合并集的算法挑战

Question

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

我的第一个尝试是形成一个 n 乘 n 的矩阵。每行/列代表一个集合。如果两个集合重叠，entry(i,j) 等于 1，entry(i,i) 存储集合 i 的长度。那么问题就变成了我们是否可以同时执行行和列操作以在左上角创建一个迹线尽可能大的对角子矩阵。

但是，我一直卡在如何有效地执行行和列操作以在左上角形成这样的对角子矩阵。

Answer 1

正如评论(最大覆盖问题)中已经指出的那样，您遇到了 NP-hart 问题。幸运的是，matlab 提供了整数线性规划的求解器。

因此我们尝试将问题简化为以下形式:

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

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

A的每一列代表一个集合。 A(i,j)=1意味着 i -th 元素在 j 中第-组，A(i,j)=0意味着 i -th 元素不在 j 中- 第一套。

现在，x代表我们选择的集合:if x_j=1比集j被选中，如果 x_j=0 - 比没有选择!

由于每个元素最多只能在一个集合中，我们选择 b=(1, 1, 1, ..., 1) :如果我们取两个包含 i 的集合-th 元素，比 i -(Ax) 的第一个元素至少为 2。

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

将其全部放入 matlab 中我们得到:

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

• f.' - 成本函数作为列
• 1:n - 所有 n x 的元素是整数
• A - 编码 n套
• ones(m,1) - b=(1,1,1...) , 有 m=100元素
• [],[] - 没有 Aeq*x=beq 形式的约束
• zeros(n,1), 0<=x必须坚持
• ones(n,1), x<=1已经从其他约束中得到遵循，但也许它会对求解器有一点帮助