受这个漫画http://xkcd.com/173/的启发
我知道有许多算法可以找到加权图的最小生成树,但是我一直在努力寻找任何能够找到最小生成“路径”的算法。
对于漫画来说,如果我们根据每对关系对每条边进行加权,那么社会最优排列将是最小跨越“路径”,即一条跨越所有顶点的路径。有人能帮忙吗?
发布于 2012-05-24 00:27:49
寻找最优哈密顿路径(也称为最优路径覆盖)是一个难题。(确定是否存在哈密顿路径是NP-完全问题) 这篇学术文章讨论了一种最优路径覆盖算法。您可以在网上搜索这些术语,以找到其他资源。我不知道有什么现成的代码。
顺便提一句,这个问题 (基本上是你的复制品)清楚地解释了为什么旅行推销员的问题不是开始的地方。
https://stackoverflow.com/questions/10729534
相似问题