查找最小集合覆蓋的最快算法

-2

找到最小集合覆蓋的最省時和最正確的算法是什麼？我不需要代碼本身。我想要一個解釋或僞代碼如何工作。
對於一個例子，我們有查找最小集合覆蓋的最快算法

Set S = {1,2,3,..,12} 

Subsets S1 = {1,2,3,4,5,6}, S2 = {5,6,7,8,9}, S3 = {1,4,7,10}, S4={2,5,7,8,11} 

S5 = {3,6,9,12}, S6 = {10,11}

的分集蓋將S3 S4üüS5。在此先感謝！

你應該提到，如果用「算法」，你的意思是**逼近算法**通過對Google的一些研究，你可以發現這是一個NP Complete問題，在1972年顯示爲NP Complete。 – Fallen

@墮落爲什麼？國際海事組織（IMO）爲這個問題尋求最有效的最優算法（在這種情況下是指數）是合理和明智的。我的意思是這仍然是一個不好的問題，因爲這些信息很容易獲得 –

@NiklasB：「尋找最小集合覆蓋的最快算法」。他可能會要求使用一個近似算法或算法來處理一個可以精確完成的小組。 – Fallen

正如評論中指出的那樣，設置封面是NP-hard。我認爲，對於「自然」情況，實際上最好的確切方法是基於integer programming。編寫一個好的整數程序求解器需要大量的工藝，所以你可能只想使用求解器庫。

2014-04-11 20:20:24

回答