查找满足条件的集合的最小子集的算法

Question

我想提取数据框的最少行数以覆盖某些列的所有元素。这是示例:

enter image description here

条件:新数据框的 list 1 封面(a，b，c)；新数据框的 list 2 封面(alpha、beta、delta、gamma)；新数据框的 project_id 覆盖 (proj1, proj2,proj3) ;

解决方法:

enter image description here

我试图用枚举来解决这个问题。最后，由于大量的计算，我放弃了这种方法。

Answer 1

这个问题是众所周知的 set cover problem 的变体。 .
由于这个问题是 NP 完全的，如果输入不是很小，找到一个最佳解决方案(意味着最小数量的元素，在你的情况下，将覆盖所有值的行)可能会花费大量时间。换句话说，这个问题的复杂性是输入大小的指数(O(2^n)，n 行数，或多或少)。

但是不要失去希望，有些方法可以让您在输入很小的情况下找到最佳解决方案，或者在输入很大的情况下找到非常令人满意的近似值。通过小输入，我的意思是数量级在 100 左右的行数，或多或少。

Branch and bound :该算法或多或少是一种“聪明”的蛮力方法，它运行得比蛮力算法快得多。它可以找到一个最佳解决方案(给定足够的时间，如果输入很大，足够的时间可能意味着一百万年)，或者它可以停止并返回迄今为止找到的最佳解决方案。我不建议你采用这种方法，但你绝对应该阅读它，它是一种非常有效且用途广泛的算法，必须知道。

Integer Linear Programming : 恕我直言，这是解决此问题的最佳方法。 ILP 允许您将程序编写为整数线性程序，然后将其提供给 ILP 求解器(市场上有很多，免费或免费，您可以找到列表 here )。如果你从未听说过线性规划，你可以看看here一些解释。
这种方法有两大优势:

• 编写解决集合封面问题的 ILP 程序非常容易，如您所见here (最多十几行)。
• ILP 求解器非常、...、非常优化，它们是专门为解决此类问题而编写的。如果您的输入少于 1000 行，它应该会找到最佳解决方案。而且，无论如何，它会找到比几乎任何程序都更好的解决方案。至少，这是一个比您花不到一周时间编写的程序更好的解决方案。

总是有可能采用贪心算法，但是集合覆盖问题不能用多项式时间算法来近似(这是对事实的过度简化，但在我们的例子中已经足够了，我们想解决一个集合覆盖的实例，而不是证明 P=NP 或研究独特的游戏猜想)。所以贪心算法的结果可能比最优解差无限多。并且运行速度只会比令人难以置信的更好的 ILP 求解器快一点。