找到访问多个城镇的最短路径
我遇到了这个问题，不知道如何解决它。有人可以帮助我吗？找到访问多个城镇的最短路径
有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
阅读维基百科条每页：https://en.wikipedia.org/wiki/Travelling_salesman_problem 这是一个NP难的问题，这意味着你的解决方案将是缓慢的。这不是无法解决的，如果你有无限的时间，你可以轻松解决它。最简单的算法是计算每个可能的路径，以起始城市开始和结束，他们的权重和最低。这是最愚蠢的方式，可能是计算量最大的。
通常情况下，使用线性规划公式解决这些问题（不要与计算机编程/编码混淆），尽管我会推荐使用启发式方法。在谷歌搜索“茶匙遗传算法”会给你各种文章，恕我直言，解决这个问题的最佳途径。这是一个非常愚蠢和聪明的算法，同时它速度快，非常快。唯一的问题是解决方案不是最优的*。如果你想知道最佳解决方案，那么你需要检查问题的最优性条件（在你的情况下，具有最低成本的任何可能的路径）。
如果你想满足最优性条件，那么很难快速解决，而不是NP-Hard分类。 （注意，最简单的方法 - 计算每条路径）是由最优性条件推断出来的，尽管可以有一个更明智的方法来确定你的计算路径是最优的。如果你发现这个问题有一个更好的最优性条件，给记者打电话，你会成为头条新闻，祝你好运。）
*如果你想要一个“好”的回答，就像一个真正的低成本的路径，但不一定是最低的，那么遗传算法是，恕我直言，要走的路。
这个问题描述的图似乎是一棵树。这不是一般的TSP，很可能在多项式时间内解决。 – moreON
听起来像旅行推销员的问题，它应该是非常难以解决的 – jazza1000
只有n-1条道路？所以这是一棵树？ ......如果我理解你所说的一切，那么它实际上是一棵植根于C的二叉树？您应该能够以某种方式利用该数据结构。 – moreON
是的，它是一棵树。但它不是那么明显，应该使用这样一个事实来证明：在一个图中不能有循环，其中至多有$ n-1 $边，并且有$ n $顶点与至少一个边相邻。 **编辑**：您必须要求图形被连接，即每个城市都可以从另一个城市到达。 –