algorithm - 查找访问多个城镇的最短路径

Question

我遇到了这个问题，但不知道如何解决。有人可以帮我解决这个问题吗？

有n个城镇由n-1条道路相连，任意2个城镇之间都有一条道路。每条道路都有一个正相关的成本。该国的城市 C 有 2 条道路与之相连(该城市也是城镇之一)，每个其他城镇都有 1 或 3 条道路与之相连。

我们想从城市 C 开始旅行，访问 m 个不同的城镇 (1 <= m <= n)，然后返回 C。但是，我们可能需要原路返回访问 m 个城镇。给出一个算法来找到访问 m 个不同城镇的最短路径。

Answer 1

这张图是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