Выбор уникального набора, представляющего номер головоломки

Question

Ниже дан набор входных данных.

1009 2000
1009 2001
1002 2002
1003 2002 

Каждая строка представляет одну группу, Number представляет идентификатор участника в группе. Задача состоит в том, чтобы выбрать минимальное количество людей, которое повторно представляет полный набор. Только один член должен быть выбран из каждой группы. 2-кортеж членов не будет повторяться. Но члены могут быть частью более чем одной группы.

Таким образом, в этом примере ответом будет 1009 и 2002, который представляет наборы. 1009 выбрано потому, что оно представляет две команды, и то же самое относится к 2002.

Я ищу, какой алгоритм можно использовать для решения этой проблемы.

Другой пример:

1009 2000
1009 2001
1002 2002
1003 2002 
1004 2003

Ответ может быть { 1009 , 2002, 1004} или { 1009, 2002, 2003}

Answer 1

На самом деле, приведенный Содведом пример показывает, что я был неправ. Это не решается краевым покрытием, так как это все еще оставляет проблему выбора фактических вершин.

Answer 2

Просто хочу заметить, что это требование

В каждой группе должен быть выбран только один участник.

не имеет особого смысла.Если вы навязываете это, эта простая проблема

1 2
2 3
3 1

не имеет решения.

Answer 3

Если кто-то интересуется, вот неуклюжий неэффективный Perl-код, который, кажется, решает проблему.Занимает ДОЛГО ... время с большим набором данных.Я уверен, что дела могут быть лучше, особенно он генерирует перестановки индекса (sequences).

#!/usr/bin/perl
# /7989834/vybor-unikalnogo-nabora-predstavlyayschego-nomer-golovolomki

use strict;
use warnings;

# Return array of arrays with every possible sequence of 0..n-1
sub sequences($);
sub sequences($)
{
    my $n = $_[0];
    my @ret;
    if( $n > 0 )
    {
        for( my $i=0; $i<$n; $i++ )
        {
            my @a = sequences( $n-1 );
            foreach my $br (@a)
            {
                my @b = @$br;
                splice( @b, $i, 0, $n-1 );
                push( @ret, \@b );
            }
        }
    }
    else
    {
        @ret = ( [] );
    }
    return @ret;
} # END sequences

# Remove elements from set which are covered by later elements in set
sub stripset($$)
{
    my( $data, $set ) = @_;
    my $strip = 0;
    my %cover;
    for( my $i=0; $i<scalar(@$set); $i++ )
    {
        my $covered;
        for( my $j=scalar(@$set)-1; $j>$i; $j-- )
        {
            if( $data->{$set->[$j]}->{$set->[$i]}
            &&  !$cover{$set->[$i]} )
            {
                $covered = 1;
                $cover{$set->[$j]} = 1;
                last;
            }
        }
        if( $covered )
        {
            $strip = $i+1;
        }
        else
        {
            last;
        }
    }
    if( $strip )
    {
        splice( @$set, 0, $strip );
    }
} # END stripset

# Load input
my %links;
while( my $line = <STDIN> )
{
    if( $line =~ /^\s*(\S+)\s+(\S+)\s*$/ )
    {
        $links{$1}->{$2} = 1;
        $links{$2}->{$1} = 1;
    }
    else
    {
        warn "INVALID INPUT LINE: $line";
    }
}

my @elems = keys(%links);
my @minset = @elems;
foreach my $seq ( sequences( scalar(@elems) ) )
{
    my @set = map( $elems[$_], @$seq );
#print "TEST set: " . join( ' ', @set ) . "\n";
    stripset( \%links, \@set );
#print "STRP set: " . join( ' ', @set ) . "\n";
    if( scalar(@set) < scalar(@minset) )
    {
        @minset = @set;
    }
}
print "Shortest set: " . join( ' ', @minset ) . "\n";

Answer 4

Вы пропустили некоторые детали, поэтому я делаю следующие предположения.Дайте мне знать, если они не правы.

• В каждой строке ровно два числа
• Никакое число, которое появляется первым в какой-либо строке, также не появляется вторым в другой строке

Итак, если вы думаете о каждом числе как о вершине в графе, и о каждой строке ввода как о ребре между двумя вершинами, вы получите двудольный граф - набор«первых чисел» и набор «вторых чисел» и ребер между ними.Теперь разбейте график на каждый из связанных компонентов .В каждом подключенном компоненте вы должны выбрать все «первые числа» или все «вторые числа».Поэтому для каждого подключенного компонента выберите любой из этих двух вариантов меньшего набора.