如何编写最大集合覆盖算法的代码？

Question

假设我们有一个有限集合S和S的子集列表。那么，集合包装问题要求在列表中是否存在k个成对不相交的子集。该问题的最优化版本——最大集合包装问题，要求在列表中找到最大数量的成对不相交的子集。

链接：http://en.wikipedia.org/wiki/Set_packing 因此，令S = {1,2,3,4,5,6,7,8,9,10}。

and `Sa = {1,2,3,4}`
and `Sb = {4,5,6}`
and `Sc = {5,6,7,8}`
and `Sd = {9,10}`

那么最大的互不相交的集合数为3（Sa、Sc、Sd）。

我没有找到有关所涉及算法的任何文章。您能否阐明一下呢？

我的方法：

按大小对集合进行排序。从最小的集合开始。如果下一个集合的任何元素都与当前集合不相交，则我们将它们合并并增加最大集合的计数。这听起来不错吗？还有更好的想法吗？

- user3080029

---

@ Niklas - 是的，这些数字是连续的 {1 到 30000+}。 - user3080029

对不起，我误解了你的问题。子集按升序排序，但数字可能不连续。原始集合是一组连续的数字列表。 - user3080029

整数规划，除非集合非常规则（例如，它们来自于社交高尔夫问题），否则使用约束规划。 - David Eisenstat

你有多少组数据？这个问题有一个简单的O(2^n)算法。 - Niklas B.

@user3080029：有一个简单的O(2^n * n^2)算法。还有一个稍微复杂一些的O(2^n)算法。独立集算法可以达到O(1.3^n)或者更好的效果。 - Niklas B.

Answer 1

正如hivert所指出的，这个问题是NP难问题，所以没有有效的方法来解决它。然而，如果你的输入相对较小，你仍然可以完成它。指数并不意味着不可能，毕竟指数问题在输入规模增长时很快变得不切实际。但对于像25个集合这样的东西，你可以很容易地进行暴力尝试。

这是一种方法。假设你有n个子集，称为S0、S1、...等等。我们可以尝试每一种子集的组合，并选择具有最大基数的那一种。只有2^25 = 33554432种选择，因此这可能是足够合理的。

一个简单的方法是注意到任何比2^N小但非负的数都代表子集的一个特定选择。查看数字的二进制表示，选择其索引对应于打开的位的集合。因此，如果数字是11，则第0、1和3位是打开的，这对应于组合[S0，S1，S3]。然后你只需验证这三个集合确实是不相交的。

你的过程如下：

1. 从0到2^N - 1迭代i
2. 对于每个i的值，使用打开的位来确定相应的子集组合。
3. 如果这些子集是成对不交的，则使用此组合更新你最好的答案（即如果它比当前最好的答案更大，则使用它）。

或者，使用回溯来生成你的子集。这两种方法在实现方面具有等价性的权衡。回溯会有一些堆栈开销，但如果你在进行检查时检查不相交性，它可以切断整个计算行。例如，如果S1和S2不相交，那么它将永远不会打扰包含这两个的任何更大的组合，从而节省一些时间。迭代方法无法以这种方式优化自身，但由于位运算和紧密循环，它快速高效。

唯一非平凡的问题在于如何检查子集是否两两不相交。 根据限制，您可以使用各种技巧来解决这个问题。

一种简单的方法是从空集合结构开始（从所选语言中选择任何内容），然后逐个从每个子集添加元素。 如果您遇到已经存在于集合中的元素，则它出现在至少两个子集中，您可以放弃这个组合。

如果原始集合S有m个元素，并且m相对较小，则可以将每个元素映射到范围[0，m-1]并为每个集合使用位掩码。 因此，如果m<=64，则可以使用Java long表示每个子集。 打开与子集中的元素对应的所有位。 这样可以进行非常快速的集合操作，因为位运算的速度快。 位运算AND对应于集合交集，而位运算OR则是并集。 您可以通过查看交集是否为空（即AND两个位掩码会给出0）来检查两个子集是否不相交。

如果元素不那么少，则仍然可以避免多次重复执行集合交。 您只有非常少的集合，因此可以预先计算哪些集合在开始时是不相交的。 您可以只存储一个布尔矩阵D，其中D [i] [j] = true当且仅当i和j不相交。 然后，您只需查找组合中的所有对以验证两两不相交性，而无需执行实际的集操作。

- Nadeem Mohsin

Answer 2

你可以通过搜索最大独立集来解决集合包装问题。您可以按以下方式对问题进行编码：

• 对于每个集合，您都会放置一个顶点
• 如果两个顶点共享一个数字，则在它们之间放置一条边。

然后，您希望获得一个最大的顶点集，而不会有两个相关的顶点。不幸的是，这是一个NP-Hard问题。任何已知的算法都是指数级别的。

- hivert

---

我应该在每次迭代中使用暴力方法来查找最小交集集合吗？我大约有25个集合。 - user3080029

通过暴力破解，25可能是可行的。有许多软件包可以做到这一点（在Sagemath中，我们使用NetworkX）。相反，如果您自己编写代码，建议您找到良好的数据结构以实现快速回溯。也许Knuth [Dancing Links]（http://en.wikipedia.org/wiki/Dancing_Links）是一个不错的选择。 - hivert

广告：我刚刚检查了一下，Sagemath中的算法似乎可以轻松解决100个节点的随机图问题。 - hivert

使用独立集问题进行求解。我曾经用它来解决类似的问题。 - coder hacker

@coderhacker 这里错过了一些快捷方式的机会，请参见 https://cs.stackexchange.com/q/86848/83094。 - AlwaysLearning