查找参观了一些城市的最短路径 [英] Find shortest path to visit a number of towns

问题描述

我碰到这个问题，不知道如何解决这个问题。是否有人可以帮助我？

I came across this problem and didn't know how to solve it. Can someone please help me with this?

有由n-1个道路连接的n个乡镇，并没有任何2个镇之间的道路。路上有一个正相关的cost.The国家的城市C有2路连接到它（这个城市也是城镇之一），和对方全镇有1或3路相连。

There are n towns connected by n-1 roads, and there is a road between any 2 towns. Each road has a positive associated cost.The country's city C has 2 roads connected to it (the city is also one of the towns), and each other town has 1 or 3 roads connected to it.

我们要开始从城市C的跳闸，请访问M个不同的城市（1＆LT; = M＆LT; = N），并回过头来C.然而，我们可能需要回溯我们的旅程，参观了米镇。给出一个算法找到最短路径的访问M个不同的城市。

We want to start a trip from city C, visit m different towns (1 <= m <= n), and come back to C. However, we might need to backtrack our trip to visit m towns. Give an algorithm to find the shortest path that visits m different towns.

推荐答案

此图是一个二叉树用root℃。

This graph is a Binary Tree with root C.

我想了一个为O（n ^ 3）算法，主要使用的动态规划

I think out an O(n^3) algorithm, mainly use Dynamic Programming

DP [I] [J] 存储的最短路径的值第i 乡镇，访Ĵ在其子树不同的城市。我们可以很容易地找到方程

dp[i][j]stores the value of the shortest path for i-thtowns, visit j different towns in its subtree. We can easily find the equation that

DP [I] [J] = MIN（DP [SONL] [K] + DP [sonr] [JK-1] + 2 * WL + 2 * WR | 1＆LT; = K＆LT; = J-1）

这意味着visitting K 在左子树城镇和 JK-1 城镇右子树。 SONL 和 sonr 是第i 镇， WL 和 WR 介于我到<$ C $的距离C> SONL 和 sonr

It means that visitting k towns in left subtree and j-k-1towns in right subtree.sonl and sonr are two sons of i-th town, wlandwrare the distance between i to sonlandsonr

这篇关于查找参观了一些城市的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！