图"Vertex cover" 暴力算法
Graph "Vertex cover" brute algorithm
Given an electrical network, which is a set of electric generators,
between which wires are stretched. A wire has current if at least one
generator is operating at one end of the wire. Find the set with
minimum count of generators that need to be turned on to provide
current to the entire network.
我找到了一些可以提供帮助的额外信息。是"Vertex cover problem".
现在我们知道它没有特殊的算法。让我们暴力破解？
正如您在问题中所指出的，这是 vertex cover problem 的一个实例。这是一个经典的 NP-hard 问题，这意味着没有已知的算法能够在有效扩展到更大的输入的同时给出准确的结果。相关的决策问题，即测试是否存在具有 k 或更少顶点的顶点覆盖，是 NP 完全问题。
因此，如果您需要真正的最小数量，那么您将无法比某种 backtracking search. If that's what you mean by "brute force" then unfortunately you're out of luck. Otherwise, if an approximation within a factor of 2 is good enough (i.e. a vertex cover with at most twice as many vertices as the true minimum), then one simple heuristic is to find a maximal matching 做得更好，然后为匹配中的每条边选择两个顶点。
Given an electrical network, which is a set of electric generators, between which wires are stretched. A wire has current if at least one generator is operating at one end of the wire. Find the set with minimum count of generators that need to be turned on to provide current to the entire network.
我找到了一些可以提供帮助的额外信息。是"Vertex cover problem".
现在我们知道它没有特殊的算法。让我们暴力破解？
正如您在问题中所指出的，这是 vertex cover problem 的一个实例。这是一个经典的 NP-hard 问题，这意味着没有已知的算法能够在有效扩展到更大的输入的同时给出准确的结果。相关的决策问题，即测试是否存在具有 k 或更少顶点的顶点覆盖，是 NP 完全问题。
因此，如果您需要真正的最小数量，那么您将无法比某种 backtracking search. If that's what you mean by "brute force" then unfortunately you're out of luck. Otherwise, if an approximation within a factor of 2 is good enough (i.e. a vertex cover with at most twice as many vertices as the true minimum), then one simple heuristic is to find a maximal matching 做得更好，然后为匹配中的每条边选择两个顶点。