我需要为一个加权无向图创建一个解决方案,穿过所有节点,使总成本最小化。多条路径,没有定义的起点,应该以一个交叉节点终止并相遇。路径数量和路径包含的节点数量没有预先确定。可以多次通过节点。
我所处理的问题属于哪种类型?可能的算法解决方案是什么? 我认为这应该是最小生成树的变体(意味着使用交叉节点作为路径的起点而不是终点)。
我所处理的问题属于哪种类型?可能的算法解决方案是什么? 我认为这应该是最小生成树的变体(意味着使用交叉节点作为路径的起点而不是终点)。
这个问题被称为最小成本哈密顿回路问题。
在这里你可以阅读更多相关信息。
你正在寻找一棵树,问题是最小生成树(MST):构建一棵跨越图中所有节点的树,并且树上边缘的成本尽可能地最小。这是一个多项式问题。Prim和Kruskal各自都有着众所周知的算法来解决这个问题。 请参见http://en.wikipedia.org/wiki/Kruskal的Kruskal算法。
注意:当树应该跨越给定节点的适当子集而不是图中的所有节点时,该问题是NP完全的。这时它被称为Steiner Minimal Tree问题。