algorithm - 如何编写最大集打包算法？

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 )

我找不到任何关于所涉及算法的文章。你能阐明同样的问题吗？

我的方法:

根据大小对集合进行排序。从最小尺寸的集合开始。如果下一个集合中没有元素与当前集合相交，那么我们合并集合并增加最大集合的数量。这听起来不错吗？有更好的想法吗？

Answer 1

正如 hivert 所指出的，这个问题是 NP-hard 问题，因此没有有效的方法来解决这个问题。但是，如果您的输入相对较小，您仍然可以完成它。毕竟，指数并不意味着不可能。只是随着输入规模的增长，指数问题很快变得不切实际。但是对于像 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 运算得到 0)。

如果你没有这么少的元素，还是可以避免多次重复设定的交点。你的集合很少，所以一开始就预先计算哪些是不相交的。您可以只存储一个 bool 矩阵 D，使得 D[i][j] = true 当且仅当 i 和 j 不相交。然后您只需查找组合中的所有对以验证成对不相交，而不是进行真正的集合操作。