寻找重叠集

我认为通过对贪婪集覆盖的某种修改,可以得到一些很好的解( 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), 但这仍然不能解决问题 计算后添加新集合 从上一个问题开始,然后在添加 新的设置只需添加新的位置