是否有任何有效的算法可以在具有偶数个顶点的完整加权图中找到具有以下属性的边集。
- 对于满足其他标准的任何集合,该集合具有最小、最大的边权重
- 每个顶点都连接到集合中的一条边
所有权重均为正
d我想不出比蛮力更好的方法,但我不认为它是 NP 难的。
是否有任何有效的算法可以在具有偶数个顶点的完整加权图中找到具有以下属性的边集。
所有权重均为正
d我想不出比蛮力更好的方法,但我不认为它是 NP 难的。
在多项式时间内解决此问题的一种方法如下:
这最大限度地减少了完美匹配包含的最大边缘,这正是您在 O(V^3) 时间内寻找的东西。
下面给出了如何做第 3 部分的资源
[1] http://www2.isye.gatech.edu/~wcook/papers/match_ijoc.pdf
[2] http://www.cs.illinois.edu/class/ sp10/cs598csc/Lectures/Lecture11.pdf
[3] http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/papers/blossom5.ps
示例 C++ 源代码可在http://ciju.wordpress.com/2008/08/10/min-cost-perfect-matching/ 获得
试试这个(我只是想到了这个,所以我既没有证据证明它会给出最佳答案,也没有证据表明它是否会在每种情况下产生解决方案):