绘制“顶点覆盖"图；蛮力算法 [英] 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.

我发现了一些可以提供帮助的其他信息.这是顶点覆盖问题".

I found some extra information that can help. It is "Vertex cover problem".

现在，我们知道它没有特殊的算法.让我们蛮力吗?

Now we know that it hasn't special algorithm. Let's bruteforce?

推荐答案

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

As you note in the question, this is an instance of the vertex cover problem. It is a classic NP-hard problem, meaning no known algorithm gives exact results while scaling efficiently to larger inputs. The associated decision problem, of testing whether a vertex cover with k or fewer vertices exists, is NP-complete.

因此，如果您需要真实的最小数字，那么您将无法做得比某种回溯搜索.如果这就是蛮力"的意思，那么不幸的是您不走运.否则，如果在2倍以内的近似值足够好(即，顶点覆盖的顶点最多是真实最小值的两倍)，则一种简单的启发式方法是找到

So, if you need the true minimum number, then you are not going to be able to do much better than some kind of 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 and then choose both vertices for each edge in the matching.

这篇关于绘制“顶点覆盖"图；蛮力算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！