c++ - 图“顶点覆盖”蛮力算法

Question

给定一个电网，它是一组发电机，电线在它们之间伸展。如果至少有一台发电机在电线的一端运行，则电线有电流。找到需要打开以向整个网络提供电流的发电机数量最少的集合。

我发现了一些可以提供帮助的额外信息。这是“顶点覆盖问题”。

现在我们知道它没有特殊的算法。让我们蛮力？

标签： c++algorithmgraph-theorygraph-algorithm

Answer 1

正如您在问题中所指出的，这是顶点覆盖问题的一个实例。这是一个经典的 NP-hard 问题，这意味着没有已知的算法可以在有效地扩展到更大的输入时给出准确的结果。测试是否存在具有k个或更少顶点的顶点覆盖的相关决策问题是 NP 完全的。

因此，如果您需要真正的最小数字，那么您将无法比某种回溯搜索做得更好。如果这就是你所说的“蛮力”，那么不幸的是你运气不好。否则，如果因子 2 内的近似值足够好（即顶点覆盖的顶点数最多是真实最小值的两倍），那么一个简单的启发式方法是找到最大匹配，然后为每个边选择两个顶点匹配。