最快的方式包括一個獨立的M + 1設置

Question

下面給出一個實際的例子：

比方說，m = 4：

// the sets for reuniting 
Set1 = { 5 , 1 , 2 } 
Set2 = { 2 , 6 , 3 } 
Set3 = { 7 , 8 , 4 } 
Set4 = { 4 , 9 , 10} 

// the set I need to form 
Set m+1: Set5 = { 1 , 2 , 3 , 4 } 

我必須找到一組索引，例如A = { 1, 2, 3 }以便U (Seti)包括Set5，其中i是A的一部分。 A的基數必須最小。

Answer 1

如果我理解這個問題正確，這裏是一個返回覆蓋SET5套的指標僞代碼：

setTmp = set5 
A = {} 
foreach i: 
    if (seti intersect setTmp) is not empty then 
    setTmp = setTmp \ setI 
    A.add(i) 
return A 

的通知，這是一個貪婪的做法，並不能保證A爲最小

Answer 2

如果我正確理解你的問題，

這是set cover problem，這是NP難。

因此，沒有算法是最優的和貪婪。檢查顯示貪婪次優方法的文章。