算法 - 找到代表所有行的单元格的最小子集

Question

我有几个列表，您可以将它们视为整数行。例如:

[1 3 5]
[3 7]
[3 5 7]
[1 5 9]
[3 9]
[1 7]
[5 9 11]

我希望找到这些行中表示的最小整数集，以便:

• 每一行至少有一个选定的整数，
• 在基数关系的情况下，选择总和最高的集合。

在我的示例中，我认为结果应该是 [5 7 9](首选 [3 5 7] 或 [1 3 11] 或......许多可能性)。

第二部分很简单(选择最高和)，但生成基数中的所有最小子集似乎很难。

你知道实现这个目标的好方法吗？

编辑

随着迭代，数据量增长缓慢，但我需要完全匹配。

Answer 1

最低基数版本是 NP-Complete。 Set Cover可以减少到这个。要求其中的最大值只会让问题变得更难。

顺便说一句，另一个关于 bool 可满足性的答案是错误的!您需要减少此问题的 bool 可满足性以显示 NP 完整性，而不是相反。

设置封面基本上是:

给出集合 S1, S2, ... Sn 的集合 X 的子集的集合，找到最小的子集合(根据集合的数量)，其并集覆盖 S1 U S2 U .. 中的所有元素。 . U Sn.

为了减少这个问题，

令 S = S1 U S2 ... U Sn。 = {x1 , x2, ..., xm}

令 C_i = { j 使得 xi 在 Sj 中 }

将 C_i 提供给我们的问题。

现在如果我们的问题可以在多项式时间内解决并且我们可以找到 C_i 元素的最小基数集，那么我们可以找到 Si 的集合覆盖，反之亦然。

这通常可以作为整数规划问题来解决(这也是 NP-Hard 问题)。

对于近似解，这可以被视为线性规划问题(具有多项式时间算法)，并且可以进行随机舍入以将小数值(LP 的解)转换为整数。

另外，不幸的是，已经证明这是 NP-hard 甚至逼近一个常数因子(事实上我相信它是 O(logn))。