1

我通常不会就 SO 提出问题，所以如果这个问题似乎不适合 SO，请告诉我（当然，我们仍然会感谢您的帮助）。

我还是一名学生，目前正在学习算法课程。我们最近了解了分支定界范式，由于我没有完全理解它，所以我尝试在我们的课本中做一些练习。我遇到了一个特殊的 Set Cover 问题实例：

令 U 是一组元素，S = {S1, S2, ..., Sn} 是 U 的一组子集，其中所有集合 Si 的并集等于 U。概述分支定界算法以找到最小S 的子集 Q，因此对于 U 中的所有元素 u，Q 中至少有两个集合，其中包含 u。具体来说，详细说明如何将问题分解为子问题以及如何计算上限和下限。

我的第一个想法是按降序对 S 中的所有集合 Si 进行排序，根据它们包含的元素数量，这些元素还没有被当前选择的 S 的子集覆盖至少两次，所以我们当前的 Q 实例。考虑递归解决这个问题，我按排序顺序选择第一个集合 Si 并进行一次递归调用，在其中我取这个集合 Si 和一个我没有的地方（意味着从那些递归调用开始，不再考虑子集） . 如果我选择它，我将遍历这个所选子集 Si 中的每个元素并为其所有元素增加一个计数器（在递归调用之前），这样我最终会知道，当一个元素已经被两个或更多选择的元素覆盖时子集。由于我为每个递归调用对未选择的集合 Si 进行排序，理论上（至少在我看来）我会一直做出目前最好的选择。而且由于我基本上创建了递归调用的二叉树，因为我总是使用当前选择的最佳子集进行一次调用，而我最终会覆盖所有 2^n 的可能性，这意味着最终我会找到最佳的解决方案。

我现在的问题是我不知道或者更确切地说我将如何实现上限和下限的启发式算法，因此算法可以丢弃二叉树中的一些路径，这永远不会比当前最好的 Q 更好。将不胜感激我能得到的任何帮助。

4

2 回答 2

0

这是一个简单的下界启发式：找到包含最大数量的尚未两次覆盖的元素的集合。（如果有多个集合具有相同的最大可能数量的这些元素，则选择哪个集合并不重要。）假设总共有 u 个这些元素，并且这个集合包含 k <= u 个。然后，您需要至少添加 u/k 组，然后才能找到解决方案。（为什么？看看你能不能证明这一点。）

这个下限也适用于常规集合覆盖问题。与分支定界一样，使用它可能会或可能不会在给定实例上产生更好的整体性能，而不是简单地使用总是返回 0 的“启发式”。

于 2021-06-13T11:06:00.660 回答
0

首先，一些建议：不要在S每次递归/循环时重新排序。排序是一项代价高昂的操作 ( O(N log N))，因此将其置于循环或递归中通常比您从中获得的成本更高。通常，您希望在开始时排序一次，然后在整个算法中利用该排序。

您选择的排序，按 S 子集的长度递减是一个很好的“贪婪”排序，所以我会说只是先做，然后不要重新排序。您不会跳过递归中不理想的子集，但是检查冗余/非理想子集仍然比每次重新排序要快。

现在你可以使用什么上限/下限？一般来说，您希望您的边界和边界检查尽可能简单和高效，因为您将经常检查它们。

考虑到这一点，上限很容易：使用您迄今为止找到的最短的集合长度解决方案。最初将您的上限设置为var bestQlength = int.MaxVal，某个最大值大于n，S 中的子集数。然后在每次递归时检查是否currentQ.length > bestQlength，如果是，则此分支超出上限并且您“修剪”它。显然，当您找到新的解决方案时，您还需要检查它是否比您当前的更好（更短） ，如果是，bestQ那么同时更新两者。bestQbestQlength

一个好的下界有点棘手，我能想到的最简单的问题是：在将新子集添加到Si您的，那么这不会以任何方式对您尝试构建的解决方案做出贡献，因此只需跳过它并继续前进到 S 中的下一个子集。currentQSicurrentQSicurrentQ

于 2021-06-14T14:34:55.270 回答