问寻找最小生成路径的算法？
EN

Stack Overflow用户

提问于 2012-05-24 00:05:20

回答 1查看 2.3K关注 0票数 5

受这个漫画http://xkcd.com/173/的启发

我知道有许多算法可以找到加权图的最小生成树，但是我一直在努力寻找任何能够找到最小生成“路径”的算法。

对于漫画来说，如果我们根据每对关系对每条边进行加权，那么社会最优排列将是最小跨越“路径”，即一条跨越所有顶点的路径。有人能帮忙吗？

发布于 2012-05-24 00:27:49

寻找最优哈密顿路径(也称为最优路径覆盖)是一个难题。(确定是否存在哈密顿路径是NP-完全问题) 这篇学术文章讨论了一种最优路径覆盖算法。您可以在网上搜索这些术语，以找到其他资源。我不知道有什么现成的代码。

顺便提一句，这个问题 (基本上是你的复制品)清楚地解释了为什么旅行推销员的问题不是开始的地方。

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/10729534

复制

相似问题

问寻找最小生成路径的算法？EN