use*_*527 5 graph graph-algorithm
灵感来自这个漫画http://xkcd.com/173/
我知道有很多算法可以找到加权图的最小生成树,但是我一直在努力寻找能够找到最小跨越"路径"的任何算法.
对于漫画,如果我们基于每个对关系加权每个边缘,那么社会最优布置将是最小跨越"路径",即跨越所有顶点的路径.有人可以帮忙吗？
Ted*_*opp 2
寻找最优哈密顿路径（也称为最优路径覆盖）是一个难题。（确定是否存在任何哈密顿路径是一个 NP 完全问题。）这篇学术文章讨论了最优路径覆盖算法等。您可以在网络上搜索这些术语以查找其他资源。我不知道有任何现成的代码。
顺便说一句，这个问题（基本上与您的问题重复）清楚地解释了为什么旅行商问题不是开始的地方。
归档时间：
13 年，6 月 前
查看次数：
1904 次
最近记录：