• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

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

算法 来源:CsIsFun 8次浏览

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

有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城镇。 sonlsonri-th镇,wlwr是之间isonlsonr


版权声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。
喜欢 (0)