algorithm - 无向图到路径的最小成本联合

Question

我必须为加权无向图创建一个解决方案，通过所有节点，总成本最低。几条没有定义起始节点的路径应该最终在一个相交节点处相遇。路径的数量和包含在路径中的节点的数量不是预先确定的。节点可以多次传递。

我正在处理什么样的问题，可能的算法作为解决方案？我想它应该是最小生成树的变体（意味着使用交叉节点作为路径的起点而不是终点）

Answer 1

这是您正在寻找的一棵树，问题是最小生成树——MST：构建一棵跨越图中所有节点的树，并且树上边的成本是最小的。这是一个多项式问题。Prim 和 Kruskal 各自都有用于解决方案的众所周知的算法。请参阅http://en.wikipedia.org/wiki/Kruskal 's_algorithm 了解 Kruskal 算法。

注意：当树应该跨越给定的适当节点子集而不是图中的所有节点时，问题是 NP 完全的。这次它被称为施泰纳最小树问题。

Answer 2

这被称为最小成本哈密顿电路问题。

在这里你可以阅读更多关于它的信息。