首页 文章

合并集的算法挑战

提问于
浏览 次
2

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

我的第一个尝试是形成一个n乘n矩阵 . 每行/每列代表一组 . 如果两个集合重叠，则条目（i，j）等于1，条目（i，i）存储集合i的长度 . 然后问题就变成我们可以同时执行行和列操作，在左上角创建一个对角子矩阵，其轨迹尽可能大 .

然而，我陷入了如何有效地执行行和列操作以在左上角形成这样的对角子矩阵 .

algorithm matlab linear-algebra

2 回答

  • 2

    正如评论中已经指出的（最大覆盖问题），你有一个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 -th集合中， A(i,j)=0 表示 i -th元素不在 j -set集合中 .

    现在， x 表示我们选择的集合：如果选择 x_j=1 而不是集合 j ，如果 x_j=0 - 未选中！

    由于每个元素必须至多在一个集合中，我们选择 b=(1, 1, 1, ..., 1) ：如果我们采用包含 i -th元素的两个集合，则 (Ax) 的 i -th元素将至少为2 .

    剩下的唯一问题是什么是 f ？我们尝试最大化联合中元素的数量，因此我们选择 f_j=-|set_j| （由于min < - >最大转换而减去）， |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 - 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 已经来自其他人的约束，但也许它会帮助解算器一点点

    回复于
  • 0

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

    回复于

相关问题