我试图用解决顶点覆盖的方法来解决集覆盖问题
输入：我们有一个基集X和X子集的集合C，因此C中的每个元素都是X 的子集
输出：C中集合中最小集合F的大小，F的所有元素的并集导致X
我知道如何解决这个问题，但我正在寻找一种启发式方法，以阻止更早地在树中走得更远。例如，现在我从C中删除每个元素，并进行递归调用，然后以这种方式检查停止点：如果（bestsofar<=F.length+1）停止
但我知道会有更好的启发式，因为例如在顶点覆盖中，我可以这样检查：如果K+1>最佳停止；其中k是覆盖边缘的结果中添加的垂直线的数量，但更好的方法是如果k+个边缘/maxdeg>=最佳停止，这要好得多。
我想要同样的东西作为封面。
有人知道吗？
从理论角度来看，顶点覆盖的启发式算法正在为顶点覆盖的松弛线性程序的对偶构造一个可行的解。套装封面也可以这样做。如果出于任何原因，你不想使用单纯形法来找到最优对偶解，那么有各种近似方法可用。您可以使用K加上项目数除以集合中的最大项目数，这推广了顶点覆盖的启发式算法。你也可以使用贪婪算法来找到一个包装，我指的是以下内容。对于顶点覆盖，这将是一组没有共同端点的边（即匹配）。每个盖子至少包含包装中每个边缘的一个端点。对于集合封面，这将是一个项目集合，因此任何集合都不包含集合中的一个以上项目。