找到访问多个城镇的最短路径

我遇到了这个问题，不知道如何解决它。有人可以帮助我吗？找到访问多个城镇的最短路径

有n个城镇由n-1条道路连接，并且任何2个城镇之间都有一条公路。每条道路都有一个积极的相关成本。该国的城市C有2条相连的道路（城市也是城市之一），而其他城镇有1条或3条道路相连。

我们想从城市C出发，参观M个不同的城镇（1 < = m < = n），然后返回C.但是，我们可能需要将我们的行程回溯到参观m个城镇。给出一个算法来找到访问m个不同城镇的最短路径。

来源

2015-10-20 CsIsFun

听起来像旅行推销员的问题，它应该是非常难以解决的 – jazza1000

只有n-1条道路？所以这是一棵树？ ......如果我理解你所说的一切，那么它实际上是一棵植根于C的二叉树？您应该能够以某种方式利用该数据结构。 – moreON

是的，它是一棵树。但它不是那么明显，应该使用这样一个事实来证明：在一个图中不能有循环，其中至多有$ n-1 $边，并且有$ n $顶点与至少一个边相邻。 **编辑**：您必须要求图形被连接，即每个城市都可以从另一个城市到达。 –

此图是一个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

来源

2015-10-20 06:50:32 throwit

我认为一个城镇可能有1或3个孩子，但是你的解决方案假定它有2个孩子。我们可以做一个检查，看看它有多少孩子，然后用相应的公式来计算dp [i] [j]？ – CsIsFun

@CsIsFun我们可以把城市C当作根，所有其他节点都有两个孩子，除了叶子 – throwit

但是我们只有一个根，有两个孩子。我认为其他节点应该有1或3个孩子 – CsIsFun

我认为，如果图是连通的最好的机会是创建包含图形中一个生成树的距离的两个儿子。你可以用Pirm算法来做。这样您就可以轻松找到每个城市之间的最短路径。

for more informations

来源

2015-10-20 07:44:30

阅读维基百科条每页：https://en.wikipedia.org/wiki/Travelling_salesman_problem 这是一个NP难的问题，这意味着你的解决方案将是缓慢的。这不是无法解决的，如果你有无限的时间，你可以轻松解决它。最简单的算法是计算每个可能的路径，以起始城市开始和结束，他们的权重和最低。这是最愚蠢的方式，可能是计算量最大的。

通常情况下，使用线性规划公式解决这些问题（不要与计算机编程/编码混淆），尽管我会推荐使用启发式方法。在谷歌搜索“茶匙遗传算法”会给你各种文章，恕我直言，解决这个问题的最佳途径。这是一个非常愚蠢和聪明的算法，同时它速度快，非常快。唯一的问题是解决方案不是最优的*。如果你想知道最佳解决方案，那么你需要检查问题的最优性条件（在你的情况下，具有最低成本的任何可能的路径）。

如果你想满足最优性条件，那么很难快速解决，而不是NP-Hard分类。（注意，最简单的方法 - 计算每条路径）是由最优性条件推断出来的，尽管可以有一个更明智的方法来确定你的计算路径是最优的。如果你发现这个问题有一个更好的最优性条件，给记者打电话，你会成为头条新闻，祝你好运。）

*如果你想要一个“好”的回答，就像一个真正的低成本的路径，但不一定是最低的，那么遗传算法是，恕我直言，要走的路。

来源

2015-10-20 07:59:01

这个问题描述的图似乎是一棵树。这不是一般的TSP，很可能在多项式时间内解决。 – moreON

找到访问多个城镇的最短路径

回答

相关问题