代码之家 › 专栏 › 技术社区 › Martin

寻找重叠集

set-theory language-agnostic algorithm

3

Martin · 技术社区 · 15 年前

我在写一封信 Digital Fountain C#中的系统。这个系统的一部分创建了整数集,我需要找到集合的组合,这些集合的创建只会给我留下一个项目集。最快的方法是什么?

Set A: 1,2,3,4,5,6
Set B: 1,2,3,4,6
Set C: 1,2,3
Set D: 5,6

Solutions:
A - B => 5
A - (C + D) => 4

我不需要找 全部的

有一点我忘了提: 我事先不知道有多少套,而是一套一套地加起来,每次都要确定是否找到了我需要的每一套。因此,算法必须是能够随着新集合的加入而分阶段运行的。

注意。C中的解决方案#获得奖励分数;)

1 回复 | 直到 15 年前

1

dfens 15 年前

我认为通过对贪婪集覆盖的某种修改,可以得到一些很好的解( http://en.wikipedia.org/wiki/Set_cover_problem

[伪代码] 所以:

1. sort sets by size descending
2.
foreach set in sets do:
  uncovered = set.size
  while uncovered > 1
    current_set = the biggest set that covers no more than (uncovered - 1) and was not used before to cover set
    uncovered = uncovered - covered_by_set(set)
    collect current_set to some array
  end
end

你可以把每个循环都当作最后一个循环设置
这只会给你带来一个每个集合的解决方案(要修复) 这可以直接改变问题设覆盖问题并使用贪心算法设置封面),例如 [1,3,4],你需要找到大小为2:[1,3], [1,4], [3,4]. 这会造成问题的要复杂得多
你可以考虑的另一种方式是进化算法(表示) 指定为位的数字,适合度函数应该增长到接近1), 但这仍然不能解决问题计算后添加新集合从上一个问题开始,然后在添加新的设置只需添加新的位置