回覆算法爲集覆蓋

Question

有人可以提供一個回溯算法來解決「集覆蓋」問題，以找到覆蓋宇宙中所有元素的最小數量的集？

貪婪的方法幾乎總是選擇比最佳數量集更多的集合。

Answer 1

這個paper使用線性規劃鬆弛來解決覆蓋問題。

基本上，LP弛豫產生良好的界限，並且可以用於識別在許多情況下最佳的解決方案。順便說一下，當我上次查看開源的LP求解器（〜2003）時，我並沒有留下深刻的印象（有些人給出了不正確的結果），但現在似乎還有一些體面的開源LP求解器。

Answer 2

你的問題需要更多的澄清 - 看起來你給了一組子集$$ S_1，\ ldots，S_n $$的集合A，這樣子集的聯合等於A，並且你想要結合仍爲A的最小數目的子集。

基本方法是用一些啓發式方法進行分支和約束。例如，如果A的特定元素僅在一個子集$$ S_i $$中，那麼你必須選擇$$ S_i $$。同樣，如果$$ S_k $$是$$ S_j $$的子集，那麼沒有理由考慮$$ S_k $$;如果元素$$ a_i $$位於$$ a_j $$所在的每個子集中，那麼您就不會考慮$$ a_i $$。

對於分支和邊界，您需要良好的邊界啓發式。下限可以來自獨立集合（如果在A中有k個元素$$ i_1，\ ldots，i_L $$，則每個如果$$ i_p $$包含在$$ A_p $$中並且$$ i_q $$被包含在$$ A_q $$中，則$$ A_p $$和$$ A_q $$是不相交的）。更好的下界來自上述的LP弛豫。

來自伯克利的Espresso邏輯最小化系統具有覆蓋發動機的高質量套件。