找到访问多个城镇的最短路径
我遇到了这个问题，不知道如何解决它。有人可以帮助我吗？找到访问多个城镇的路径" title="最短路径">最短路径
有n个城镇由n-1条道路连接，并且任何2个城镇之间都有一条公路。每条道路都有一个积极的相关成本。该国的城市C有2条相连的道路（城市也是城市之一），而其他城镇有1条或3条道路相连。
我们想从城市C出发，参观M个不同的城镇（1 < = m < = n），然后返回C.但是，我们可能需要将我们的行程回溯到参观m个城镇。给出一个算法来找到访问m个不同城镇的最短路径。
回答：
此图是一个Binary Tree与根C.
我想出来一个O(n^3)算法，主要使用Dynamic Programming
dp[i][j]商店为i-th城镇的最短路径的价值，在其子树参观j不同的城市。我们可以很容易地找到方程
dp[i][j] = min (dp[sonl][k] + dp[sonr][j-k-1] + 2*wl + 2*wr | 1<=k<=j-1)
这意味着，在望京左子树k城镇和右子树j-k-1城镇。 sonl和sonr是i-th镇，wl和wr是之间i到sonl和sonr
回答：
我认为，如果图是连通的最好的机会是创建包含图形中一个生成树的距离的两个儿子。你可以用Pirm算法来做。这样您就可以轻松找到每个城市之间的最短路径。
for more informations
回答：
阅读维基百科条每页：https://en.wikipedia.org/wiki/Travelling_salesman_problem 这是一个NP难的问题，这意味着你的解决方案将是缓慢的。这不是无法解决的，如果你有无限的时间，你可以轻松解决它。最简单的算法是计算每个可能的路径，以起始城市开始和结束，他们的权重和最低。这是最愚蠢的方式，可能是计算量最大的。
通常情况下，使用线性规划公式解决这些问题（不要与计算机编程/编码混淆），尽管我会推荐使用启发式方法。在谷歌搜索“茶匙遗传算法”会给你各种文章，恕我直言，解决这个问题的最佳途径。这是一个非常愚蠢和聪明的算法，同时它速度快，非常快。唯一的问题是解决方案不是最优的*。如果你想知道最佳解决方案，那么你需要检查问题的最优性条件（在你的情况下，具有最低成本的任何可能的路径）。
如果你想满足最优性条件，那么很难快速解决，而不是NP-Hard分类。 （注意，最简单的方法 - 计算每条路径）是由最优性条件推断出来的，尽管可以有一个更明智的方法来确定你的计算路径是最优的。如果你发现这个问题有一个更好的最优性条件，给记者打电话，你会成为头条新闻，祝你好运。）
*如果你想要一个“好”的回答，就像一个真正的低成本的路径，但不一定是最低的，那么遗传算法是，恕我直言，要走的路。
以上是 找到访问多个城镇的最短路径 的全部内容， 来源链接： utcz.com/qa/260494.html
