合并集的算法挑战

Question

给定n组数。每组包含一些从1到100的数字。如何在特定规则下选择合并为最长集的集合，只有两个不重叠的集合才能合并。1,2,3可以与4,5合并，但不能与3,4合并。什么是合并成最长集的有效算法？

我的第一次尝试是构造n乘n矩阵。每一行/列表示一组。条目( i，j)等于1，如果两组重叠，条目(i，i)存储集i的长度。然后问题是我们可以同时执行行和列操作，在左上角创建一个跟踪尽可能大的对角线子矩阵。

然而，我被困在如何有效地执行行和列操作，以形成这样一个对角线子矩阵在左上角。

Answer 1

正如在注释(最大覆盖率问题)中已经指出的，您有一个NP-hart问题。幸运的是，matlab为整数线性规划提供了求解器。

因此，我们试图将问题简化为以下形式：

min f*x subject to Ax<=b , 0<=x

有n个集合，我们可以将一个集合编码为0和1s的向量。例如，(1,1,1,0,0,...)表示{1,2,3}和(0,0,1,1,0,0...) - {3,4}。

A的每一列都表示一个集合。A(i,j)=1表示i-th元素位于j-th集中，A(i,j)=0表示i-th元素不在j-th集中。

现在，x代表我们选择的集合:如果x_j=1比set j被选中，如果x_j=0 -而不是选择！

因为每个元素最多必须在一个集合中，所以我们选择b=(1, 1, 1, ..., 1)：如果我们使用两个包含i-th元素的集合，那么(Ax)的i-th元素至少是2。

剩下的唯一问题是f是什么？我们试图最大化联合中的元素数，因此我们选择f_j=-|set_j| (由于最小->最大转换而减去)，在j-th集中选择|set_j| -元素数。

在matlab中我们得到：

f=-sum(A)
xopt=intlinprog(f.',1:n,A,ones(m,1),[],[],zeros(n,1),ones(n,1))

• f.' -作为列的成本函数
• 1:n - x的所有n元素都是整数
• A -编码n集
• ones(m,1) - b=(1,1,1...)，有m=100元素
• [],[] -没有对表单Aeq*x=beq的约束
• zeros(n,1), 0<=x必须保持
• ones(n,1), x<=1已经跟随了其他约束，但是它可能会对求解者有所帮助。

Answer 2

您可以将集合表示为位字段。按位运算产生零将表示不重叠集。根据基础数据类型的宽度，您可能需要执行多个和操作。例如，使用64位机器字大小，我需要两个单词作为位字段来覆盖1到100。