3

我正在用 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

我不需要找到所有的组合，只要找到尽可能多的唯一数字就够了。这可以用来创建更有效的算法。

很重要的一点我忘了说：我事先不知道有多少个集合，而是一个一个地添加，并且每次都必须确定是否找到了我需要的每个数字。因此，算法必须是可以在添加新集合时分阶段运行的东西。

NB。C# 中的解决方案获得加分；）

4

1 回答 1

1

我认为通过使用贪婪集覆盖（ 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

编辑：

  • 您可以为最后一组省略 foreach 循环
  • 这将为每个集合带来不超过一个解决方案（要解决此问题，您可以将问题直接更改为集合覆盖问题并使用贪婪集合覆盖），例如，如果您排列 [1,3,4]，您需要找到SCV 问题的所有大小 = 2 的子集的解决方案：[1,3]、[1,4]、[3,4]。它会使问题变得更加复杂
  • 您可能会考虑的另一种方法是进化算法（这里的表示将非常简单，将指定的数字视为位，适应度函数应该接近 1），但这仍然不能解决在计算后添加新集合的问题（也许当你从上一个问题中获得最佳种群，然后在添加新集合后在染色体中添加新位置）
于 2010-10-04T13:35:58.203 回答