我必须为加权无向图创建一个解决方案，通过所有节点，总成本最低 . 没有定义的起始节点的若干路径应该在一个交叉节点处结束并相遇 . 路径的数量和路径中包括的节点的数量不是预先确定的 . 节点可以多次传递 .
我处理什么样的问题，可能的算法作为解决方案？我想它应该是最小生成树的变体（意味着使用交叉点节点作为路径的起点而不是终点）
它被称为最小成本哈密顿电路问题 .
Here您可以阅读更多相关信息 .
它是您正在寻找的树，问题是最小生成树 - MST：构建一个跨越图中所有节点的树，并且树上边缘的成本是最小的 . 这是一个多项式问题 . Prim和Kruskal都有众所周知的解决方案算法 . 请参见http://en.wikipedia.org/wiki/Kruskal 's_algorithm for Kruskal' s算法 .
注意：当树应该跨越给定的适当节点子集而不是图中的所有节点时，问题是NP完全的 . 这次它被称为Steiner Minimal Tree问题 .
2 回答
它被称为最小成本哈密顿电路问题 .
Here您可以阅读更多相关信息 .
它是您正在寻找的树，问题是最小生成树 - MST：构建一个跨越图中所有节点的树，并且树上边缘的成本是最小的 . 这是一个多项式问题 . Prim和Kruskal都有众所周知的解决方案算法 . 请参见http://en.wikipedia.org/wiki/Kruskal 's_algorithm for Kruskal' s算法 .
注意：当树应该跨越给定的适当节点子集而不是图中的所有节点时，问题是NP完全的 . 这次它被称为Steiner Minimal Tree问题 .