algorithm - 寻找更好的绑定(bind)来更早地停止设置封面

Question

我正在尝试以解决顶点覆盖的方式解决集合覆盖问题

输入:我们有一个基集 X 和 X 子集的集合 C，因此 C 中的每个元素都是 X 的一个子集

输出:C 中集合的最小集合 F 的大小，其方式是 F 的所有元素的并集产生 X

我知道如何解决这个问题，但我正在寻找一种启发式方法来更早地停止在树中走得更远。例如，现在我从 C 中删除每个元素并进行递归调用，然后我以这种方式检查停止点:if(bestsofar <= F.length+1) stop

但我知道会有更好的启发式方法，因为例如在顶点覆盖中我可以这样检查:if K+1 >best stop;其中 k 是结果中添加的顶点数以覆盖边，但更好的方法是如果 K+ number Edges/maxdeg >=best stop 哪个更好。

我想要 set-cover 的同样东西。

有人知道吗？

Answer 1

从理论的角度来看，您的顶点覆盖启发式算法正在为松弛的 linear program 的对偶构造一个可行的解决方案。用于顶点覆盖。布景封面也可以这样做。如果出于某种原因您不想使用单纯形法来寻找最优对偶解，则可以使用多种近似值。您可以使用 K 加上项目数除以集合中的最大项目数，这概括了顶点覆盖的启发式。您还可以使用贪心算法来查找包装，我的意思如下。对于顶点覆盖，这将是一组没有共同端点的边(即匹配)。每个盖子包含包装中每个边缘的至少一个端点。对于集合封面，这将是一组项目，这样任何集合都包含集合中的一个以上项目。