集合覆盖问题的扩展版本
我通常不会在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中的每个元素，并为它的所有元素增加一个计数器(在递归调用之前)，这样我最终就会知道，当一个元素已经被两个或更多选择的子集覆盖时。因为我为每个递归调用对未选择的集合Si进行了排序，所以理论上(至少在我的心目中)我将始终做出当前可能的最佳选择。由于我基本上创建了一个递归调用的二叉树，因为我总是使用当前选择的最佳子集进行调用，而在不选择的情况下，我将最终覆盖所有2^n个可能性，这意味着最终我将找到最优解。
我现在的问题是，我不知道或者更确切地说，我不知道如何实现一个启发式的上限和下限，所以算法可以丢弃二叉树中的一些路径，这永远不会比当前最好的Q更好。我将非常感谢任何我可以得到的帮助。
回答 2
Stack Overflow用户
发布于 2021-06-13 19:06:01
这里有一个简单的下界启发式:找到包含最大数量的尚未两次覆盖的元素的集合。(如果有多个集合具有相同的、可能的最大数量的元素，则选择哪个集合并不重要。)假设总共有u个这样的元素，这个集合包含k个<= u个元素。然后，在获得解决方案之前，您需要添加至少u/k个进一步的集合。(为什么？看看你是否能证明这一点。)
这个下界也适用于常规集合覆盖问题。与通常的分支和界限一样，与简单地使用总是返回0的“启发式”相比，使用它可能会也可能不会在给定实例上产生更好的整体性能。
Stack Overflow用户
发布于 2021-06-14 22:34:55
首先，一些建议:不要在每次递归/循环时都对S进行重新排序。排序是一种代价高昂的操作(O(N log N))，因此将其放入循环或递归中的成本通常高于您从中获得的收益。通常，您希望在开始时进行一次排序，然后在整个算法中利用这种排序。
你选择的排序，按S子集的长度递减是一个很好的“贪婪”排序，所以我想说的是，只需提前进行排序，之后就不需要重新排序了。您不能跳过递归中不理想的子集，但检查冗余/非理想子集仍然比每次重新排序要快。
现在你可以使用的上下限是多少？一般来说，你希望你的边界和边界检查尽可能简单和有效，因为你将会检查它们很多。
考虑到这一点，一个上限很容易:使用到目前为止找到的最短集合长度解决方案。最初将上界设置为var bestQlength = int.MaxVal，某个大于n的最大值，S中的子集数量。然后在每次递归中检查是否为currentQ.length > bestQlength，如果是，则此分支超出上界，您将对其进行“修剪”。显然，当你找到一个新的解决方案时，你还需要检查它是否比你当前的bestQ更好(更短)，如果是，那么同时更新bestQ和bestQlength。
一个好的下限有点棘手，对于这个问题，我能想到的最简单的是:在您将一个新的子集Si添加到您的currentQ之前，检查Si是否有任何元素还没有在currentQ中两次或更多次，如果没有，那么这个Si就不能以任何方式对您试图构建的currentQ解决方案做出贡献，所以跳过它，转到S中的下一个子集。
https://stackoverflow.com/questions/67950706
复制相似问题
腾讯云开发者
