graph - 找到“最小跨越路径”的算法？

Question

灵感来自这部漫画http://xkcd.com/173/

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

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

Answer 1

寻找最优哈密顿路径（也称为最优路径覆盖）是一个难题。（确定是否存在任何哈密顿路径是一个 NP 完全问题。）这篇学术文章讨论了最优路径覆盖算法等内容。您可以在网上搜索这些术语以查找其他资源。我不知道任何现成的代码。

顺便说一句，这个问题（基本上是你的问题）清楚地解释了为什么旅行商问题不是开始的地方。