寻找“最小生成路径”的算法？

Question

6

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

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

对于这个漫画，如果我们基于每对人之间的关系给每条边赋权重，那么社交最优排列将是最小生成路径，即涵盖所有顶点的路径。有人能帮忙吗？

- user31527

2

这与寻找最小哈密顿路径有什么不同吗？ - Ted Hopp

正确的观察。另一个有趣的案例是相关问题在复杂性上的差异：最小生成树=简单，最短路径生成树/哈密顿回路=困难。 - Ray Toal

如果您对社交约束条件进行一些假设，可能可以使用修改后的哈夫曼算法来解决这个问题。 - Sam Dufel

可能是 https://dev59.com/oVvUa4cB1Zd3GeqPpg7A 的重复问题。 - Ted Hopp

谢谢大家的回复，我找到了这个链接https://dev59.com/DF_Va4cB1Zd3GeqPYOtE，它表明没有比暴力算法更好的算法。 - user31527

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ted Hopp · Accepted Answer

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

顺便提一下，这个问题（基本上与你的问题重复）清楚地解释了旅行商问题不是开始的好地方。