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

-2

比方說，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的基數必須最小。

來源

2011-12-19 user1064088

真的很難理解它，有什麼問題嗎？ – 2011-12-19 09:59:27

我不明白這個例子中的一個詞.. – 2011-12-19 10:07:55

他有一套F和一套S系列。想要找到F-G的子系列，使得| G |是最小的，S是G中的集合總和的一個子集 – soulcheck 2011-12-19 10:12:14

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

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

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

來源

2011-12-19 10:13:54 yurib

這返回一個覆蓋set5的族，但不是最小的一個族。 – soulcheck 2011-12-19 10:15:50

@soulcheck你是對的，我只是把它添加到 – yurib 2011-12-19 10:16:30

後，如果它不能保證A是最小的，那麼它不是一個真正的問題的答案。 – soulcheck 2011-12-19 10:18:32

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

這是set cover problem，這是NP難。

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

來源

2011-12-19 10:21:04

是的，這是問題所在。感謝這個鏈接，但這個貪婪的算法似乎有一個相當大的複雜性，我希望爲更快的事情提供一個創新的ideea。 – user1064088 2011-12-19 11:56:00

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

回答

相關問題