选择唯一的数字集合来表示数独谜题

Question

以下是给定的输入集。

1009 2000
1009 2001
1002 2002
1003 2002 

每一行代表一个小组，数字代表该小组成员的ID。问题是选择最少的人来代表给定的完整集合。每个小组只能选择一个成员。2元组成员不会重复。但成员可以是多个小组的一部分。

因此，在这个例子中，答案是代表两个团队的1009和2002。选择1009是因为它代表了两个团队，2002也是同样的情况。

我正在寻找什么算法可以用来解决这个问题。

另一个例子：

1009 2000
1009 2001
1002 2002
1003 2002 
1004 2003

答案可能是{ 1009 , 2002, 1004}或{ 1009, 2002, 2003}

- Avinash

Answer 1

实际上，Sodved给出的例子表明我错了。这个问题并不能通过边覆盖来解决，因为这仍然需要选择实际的顶点。

- Frank

---

这实际上不是最小顶点问题吗？因为他想要最小的ID集合。我用perl编写了一个“尝试每个组合”的解决方案，对于大约16个点它需要很长时间。http://en.wikipedia.org/wiki/Vertex_cover - Sodved

不，这不是最小顶点问题（顺便说一下，它是NP完全问题）。要求只选择每个组的一个成员与顶点覆盖情况相冲突，在顶点覆盖情况下，您不关心选择由边连接的顶点。 - Frank

其实不用理我。这更像是一个edg问题，尽管最终结果是顶点。我想这张图片显示了他想要的东西，我对吗？http://i.min.us/icnaFo.png - Sodved

你是对的，实际上你的例子表明边覆盖不足够，因为它只给出了3条边，但并没有直接涵盖这两个顶点。 - Frank

Answer 2

如果有人感兴趣，这里有一些笨拙而低效的Perl代码，似乎可以解决问题。在处理大数据集时需要很长时间。我相信事情可以做得更好，特别是生成索引排列（sequences）方面。

#!/usr/bin/perl
# https://dev59.com/glnUa4cB1Zd3GeqPYTnG

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";

- Sodved

Answer 3

只是想提醒一下这个要求：

每个组只能选择一个成员。

并没有太多意义。如果你强制执行它，这个简单的问题

1 2
2 3
3 1

没有解决方案。

- n. m.

---

从第一组中选择1个，从第二组和第三组中各选择3个。 - Avinash

2和3在同一组。 - n. m.

Answer 4

你漏掉了一些细节，所以我做出以下假设，请告诉我它们是否正确。

• 每行恰好有两个数字
• 没有一个数字在某行上首次出现，也在另一行上第二次出现

因此，如果将每个数字视为图中的一个顶点，并将每行输入视为两个顶点之间的边，则您拥有的是一个二分图——一组“第一个数字”和一组“第二个数字”，以及它们之间的边。现在，将该图分解成其每个连通组件。在每个连通组件中，您要么必须选择所有“第一个数字”，要么必须选择所有“第二个数字”。因此，在每个连通组件中，选择其中较小的一个选项。

- Eddy Ferreira