3

所以，我有几个集合，我需要找到最少数量的集合，其中包含所有集合中的至少一个元素。为了更具体，我有一组服务器名称，每个服务器都有一个服务窗口。给定特定的持续时间，我想找到覆盖所有给定服务器的最小服务窗口集。

我已经有代码为每台所需的机器生成所有不重叠的 N 分钟时间段的列表。我打算通过生成所有可能的组合来强制它，并选择具有最少数量的唯一元素的组合，但这似乎非常低效，即使我首先将集合减少到所有主机的唯一窗口（尤其是更多比几个系统）。

然后我想我会做一些事情，比如按适合每个时间槽的主机数量对时间槽进行排序，选择主机数量最多的槽，然后为未分配的主机重新生成所有槽的列表，选择最多流行的插槽，重新计算等，直到所有主机都被考虑在内。虽然这会给我一个答案，但它并没有真正让我有机会选择最平衡的集合 - 次要目标是找到一组服务窗口，每个服务的主机数量的标准偏差最小窗户。因此，如果我有 100 台主机，我想优先选择每个窗口提供大约 50 台主机的窗口，而不是执行上述算法可能找到的三个“98、1 和 1”窗口。但如果我的选项是“98, 1, 1” 或 10 个窗口，每个窗口 10 个。我宁愿做这三个。

无论如何，似乎某种图形可以用来表示这个问题，但在我的 CS 路径中，我更多地关注硬件而不是软件，解决图形问题从来都不是我的强项。所以我什至会感谢一些关于在哪里阅读更多关于这个特定问题或适当搜索词的建议。:)

4

2 回答 2

2

这是集合覆盖优化问题，它是 NP 难的。这意味着在最坏的情况下你不能比蛮力做得更好。也就是说，您可以快速找到一些组合安排。但是您绝对可以简化问题 - 特别是使用真实世界的数据。

我将从对数据进行几次转换开始。把你的集合想象成一个布尔网格。每列代表一个服务器，每一行代表一个集合。在一个单元中为真意味着服务器存在于该集合中。

  1. 您可能有多个服务器属于完全相同的集合。也就是说，这个矩阵中很可能会有相同的列。您可以删除任何重复的列。因此，如果 A 和 B 恰好具有保存服务窗口，则获取包含 A 的覆盖也将包含 B。您可以通过按此列中的值对每个服务器进行哈希处理来快速完成此操作，然后检查同一哈希存储桶中的每个服务器相同的集合成员。只保留一台服务器，并创建一个“随行”服务器列表。例如。从现在开始，这些服务器将被视为您的集合中的单个成员。

  2. 删除作为单个其他集合的子集的任何集合。例如，如果您有 {1,2,3} 和 {1,2}。从问题中删除 {1,2}。为您的覆盖物选择集合时，{1,2,3} 始终是更好的选择。所以转储子集 - 例如删除所有这些行。

  3. 遍历每台服务器（例如每一列）。每台服务器只存在于一个集合中（例如列中的一个为真），那么该集合必须是解决方案的一部分。因此，将该集合添加到解决方案中，并将其从矩阵中删除。现在您可以从矩阵中删除已删除集合中的任何列。假设服务器 A 仅存在于集合 1 中，即 { A,B,C}。井集 1必须是解决方案的一部分。如果是，那么我自动知道服务器 A、B、C 将自动被覆盖。所以我从矩阵和 A、B、C 的列中删除了第 1 组。

  4. 删除每组中的所有服务器。他们将在任何解决方案中。

在此之后，除非您的数据集是“反常的”，否则您的真正问题集应该会大大减少。现实世界的数据可能会足够有序，以至于一堆行和列都不会出现问题。

我敢肯定，有一些很好的方法可以找到答案，在实践中，这些方法可以让您在比蛮力时间更好的真实世界数据中获得非常接近最佳覆盖。

我会考虑 DP 或 A-Star 搜索解决方案。我没时间了。我以后可能会画出来。

于 2012-07-11T11:25:42.933 回答
1

考虑与每个时间段相关联的单独服务器集。您正在寻找构建这些集合的一个子集，使其联合包含所有服务器。这被称为集合覆盖问题，已被证明是 NP 完全的。这意味着您无法比您在问题中描述的蛮力方法做得更好，因此请尽可能减少来自所有主机的唯一窗口数量。

PS我不确定为什么templatetypedef删除了他的答案-我认为这是正确的。

于 2012-07-11T03:52:09.573 回答