包含所有給定元素的容器的最小數量

假設C涉及一組容器{c1,c2,c3....cn}，其中這些容器中的每一個都包含一組有限的整數{i1,i2,i3...im}。此外，假設一個整數可能存在於多個容器中。給定一組有限整數S{s1,s2,s3...sz}，找到包含S中所有整數的最小子集C的大小。包含所有給定元素的容器的最小數量

請注意，可能有成千上萬個容器，每個容器都有數百個整數。因此，蠻力對於解決這個問題很慢。

我試圖用貪婪算法解決這個問題。也就是說，每次我選擇集合中數量最多的容器時，集合S，但我失敗了！

任何人都可以提出一個快速的算法來解決這個問題嗎？

來源

2012-08-25 Traveling Salesman

該算法如何與生物信息學相關？ –

這是衆所周知的[設置封面問題]（http://en.wikipedia.org/wiki/Set_cover_problem）。它是NP完全的，因此沒有高效的算法是已知的。貪婪算法可以完成（除非P = NP）。 –

我想找到包含所有給定基因的GO術語的最小窗口大小....爲了簡單起見，我使用了整數和容器。 –

這是衆所周知的set cover problem。它是NP-hard - 事實上，它的決策版本是NP規範的完整問題之一，也是Karp's 1972 paper中包含的21個問題之一，因此沒有高效的算法。除非你能夠找出問題的一些特殊的額外結構，否則你將不得不滿足一個近似的結果：也就是說，C的一個子集，其結合包含S，但它不一定是C的這種子集。

greedy algorithm可能是您最好的選擇：它找到的集合集合不超過最小這樣的集合的大小O（log | C |）倍。

你說你無法讓貪婪的算法工作。我認爲這可能是因爲你沒有正確實施它。你描述你的算法是這樣的：

每次我選擇最大號的集合S

的整數，但在平時的貪心算法規則的容器在每個階段選擇

的集合S 中的整數數量最多的容器，它們不在目前選擇的任何容器中。

來源

2012-08-25 16:43:27

也許有一些我在這裏失蹤，假設我們有S = {1,2,3,4,5,6} ，我們有3個容器，c1 = {1,3,4,6}，c2 = {1,2,3}，c3 = {4,5,6} 實現貪婪算法...我會在第一階段c1中選擇，因爲它是最大的未被覆蓋的元素....之後，我會採取c2然後c3。這顯然不是正確的解決方案......因爲我只能採用c2和c3 ......你怎麼看？ –

由於問題是NP完全的，因此不能期望在合理的時間內計算最小的覆蓋。貪婪算法因此是*近似算法*：它計算* a *覆蓋，但不總是*最小*覆蓋。如果您發現最小的封面對您很重要，那麼您運氣不好。 –

謝謝Gareth Rees的幫助。 –

包含所有給定元素的容器的最小數量

回答

相關問題