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

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难的,所以没有有效的方法来做到这一点.但是,如果您的输入相对较小,您仍然可以将其拉出.毕竟,指数并不意味着不可能.随着输入大小的增加,指数问题很快变得不切实际.但对于像25集这样的东西,你可以轻松地强行它.

这是一种方法.假设您有n个子集,称为S0,S1,......等.我们可以尝试每个子集组合,并选择具有最大基数的子集.只有2 ^ 25 = 33554432的选择,所以这可能是合理的.

一种简单的方法是注意严格低于2 ^ N的任何非负数表示特定的子集选择.查看数字的二进制表示,并选择其索引对应于打开的位的集合.因此,如果数字是11,则第0,第1和第3位开启,这对应于组合[S0,S1,S3].然后你只是验证这三组实际上是不相交的.

您的程序如下:

1. 迭代i从0到2 ^ N - 1
2. 对于i的每个值,使用打开的位来计算相应的子集组合.
3. 如果这些子集是成对不相交的,请使用此组合更新您的最佳答案(例如,如果它大于您当前的最佳值,请使用此组合).

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

这里唯一的重要问题是如何检查子集是否成对不相交.根据约束条件,你可以在这里使用各种技巧.

一个简单的方法是从空集结构开始(从您选择的语言中选择您想要的任何内容)并逐个添加每个子集中的元素.如果您曾经遇到过已经在集合中的元素,那么它至少会出现在两个子集中,您可以放弃这个组合.

如果原始集合S具有m个元素,并且m相对较小,则可以将它们中的每一个映射到范围[0,m-1]并对每个集合使用位掩码.因此,如果m <= 64,则可以使用Java long来表示每个子集.打开与子集中的元素对应的所有位.由于按位操作的速度,这允许快速设置操作.按位AND对应于集合交集,按位OR是并集.您可以通过查看交集是否为空来检查两个子集是否不相交(即,对两个位掩码进行AND运算得到0).

如果您没有这么少的元素,您仍然可以避免多次重复设置的交叉点.你有很少的集合,所以预先计算哪些集合在开始时是不相交的.你可以只存储一个布尔矩阵D,这样如果f i和j是不相交的,则D [i] [j] =真.然后,您只需查找组合中的所有对,以验证成对不相交,而不是进行实际的设置操作.