集合覆盖的回溯算法

Question

有没有人可以提供一个回溯算法来解决“集合覆盖”问题，以找到覆盖宇宙中所有元素的最小集合数量？

贪婪方法几乎总是选择比最佳集合数量更多的集合。

Answer 1

该paper使用线性规划松弛来解决覆盖问题。

基本上，LP松弛产生了良好的边界，并且在许多情况下可以用来确定最优解。顺便说一句，当我上一次查看开源LP解算器(约2003年)时，我并不印象深刻(有些给出了不正确的结果)，但现在似乎有一些不错的开源LP解算器。

Answer 2

你的问题需要更多的澄清--似乎你得到了一个集合A的子集族$$S_1，\ldots，S_n$$，使得这些子集的并集等于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逻辑最小化系统有一个非常高质量的集合覆盖引擎。