给一个电网，它是一组发电机，电线之间被拉伸。电线至少有一根电流发电机在电线的一端工作。找到与需要打开电源以提供最小数量的发电机当前到整个网络。
我发现了一些可以帮助您的额外信息。它是“顶点覆盖问题”。
现在我们知道它没有特殊的算法。让我们蛮力吗？
正如您在问题中指出的，这是vertex cover problem的一个实例。这是一个经典的NP难题，这意味着在有效地扩展到较大的输入时，没有已知的算法能给出准确的结果。测试是否存在k或更少的顶点的顶点覆盖率的相关决策问题是NP完全的。
因此，如果您需要真实的最小数字，那么您将无法比某种backtracking search做得更好。如果这就是“蛮力”的意思，那么不幸的是您不走运。否则，如果因子2内的近似值足够好（即，顶点覆盖的顶点最多是真实最小值的两倍），则一种简单的试探法是找到maximal matching，然后为每个边选择两个顶点在匹配中。