選擇代表數字拼圖的唯一集合

以下是給出的輸入集。選擇代表數字拼圖的唯一集合

每行代表一個組，Number代表組中的成員的ID。問題是選擇重新呈現完整給定集合的最少人數。每個組只能選擇一名成員。二元組成員不會重複。但是，成員可以成爲不止一個組的一部分。

所以在這個例子中，答案是1009和2002，它表示這些集合。選擇1009是因爲它代表兩個團隊，2002的情況也是如此。

我在找什麼算法可以用來解決這個問題。

又如：

答案可以{ 1009 , 2002, 1004}或{ 1009, 2002, 2003}

來源

2011-07-14 Avinash

實際上，通過Sodved給出的例子表明，我錯了。它不能被邊緣覆蓋物解決，因爲這仍然留下選擇實際頂點的問題。

來源

2011-07-14 06:36:22 Frank

它不是最小化頂點問題嗎？他想要最小的一組ID？ HTTP：//en.wikipedia。org/wiki/Vertex_cover我在perl中敲了一個「嘗試每個組合」的解決方案，並花了大約16分的時間。 – Sodved

不，它不是最小頂點問題（這是btw，NP-complete）。要求每個組中只有一個成員必須與頂點覆蓋情況相沖突，在這種情況下，您不關心選擇由邊連接的頂點。 – Frank

其實不理我。它更像是一個edg問題，即使最終的結果是頂點。我是否正確地認爲這張照片展示了他之後的事情？ http://i.min.us/icnaFo.png – Sodved

你留下了一些細節，所以我做了以下假設。讓我知道他們是否錯了。

正好有每行
兩個數字沒有首先出現在某些行號也第二次出現在一些其他線路

所以，如果你認爲每個數字爲圖表中一個頂點，並且每行輸入作爲兩個頂點之間的邊，您得到的是一個bipartite graph - 一組「第一個數字」和一組「第二個數字」，以及它們之間的邊。現在，將圖分解爲它的每個connected components。在每個連接的組件中，您必須選取所有「第一個數字」或全部「第二個數字」。因此，對於每個連接的組件，挑選這兩個選項中較小的一個。

來源

2011-07-14 06:57:42

如果任何人有點麻煩，這裏有一些笨拙的inefficent Perl代碼，似乎解決這個問題。需要很長時間才能處理大量數據。我相信事情可以做的更好，尤其是他這一代的索引排列（sequences）。

#!/usr/bin/perl 
# http://stackoverflow.com/questions/6689147/ 

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

來源

2011-07-14 08:15:42 Sodved

只是要注意，這個要求

只有一個成員都應該從每個組進行選擇。

沒有多大意義。如果你執行它，這個簡單的問題

1 2 
2 3 
3 1

沒有解決方案。

來源

2011-07-14 08:49:40

從組1中選擇1，從組2中選擇3。 – Avinash

2和3在同一組中。 –

選擇代表數字拼圖的唯一集合

回答

相關問題