动态规划：穿越城市 [英] dynamic programming : traversal of cities

问题描述

我遇到了这样一个问题：

I came across this question:

有两个人。有n个城市的有序序列，并且每对城市之间的距离是给定的。您必须将城市划分成两个子（不一定是连续的），使得某甲访问所有城市的第一个序列（按顺序），某乙访问所有城市在第二序列（按顺序），而这样的总和由A和B的总行驶距离最小化。最初假设某甲和某乙开始在各自的子序列的第一个城市。

There are two persons. There is an ordered sequence of n cities, and the distances between every pair of cities is given. You must partition the cities into two subsequences (not necessarily contiguous) such that person A visits all cities in the first subsequence (in order), person B visits all cities in the second subsequence (in order), and such that the sum of the total distances travelled by A and B is minimized. Assume that person A and person B start initially at the first city in their respective subsequences.

我找了它的答案，得到的答案是：
让C [I，J]是最低的行驶距离，如果第一人停止在城市，我和第二的城市学家假设I＆LT; Ĵ

I looked for its answer and the answer was:
Let c[i,j] be the minimum distance travelled if first person stops at city i and second at city j. Assume i< j

C [0，D] =的总和（D [K，K + 1]）对于k从1到J-1
C [I，J] = MIN（C [K，J] + D [K，I]），如果我！= 0，其中0

该解决方案也可以在质询10 此处

c[0,j]= summation of (d[k,k+1]) for k from 1 to j-1
c[i,j] = min(c[k,j]+ d[k,i]) if i!=0 where 0

The solution can also be seen at question 10 here

现在，我的问题是：
1.该解决方案具有没有定义I = 1（如则k没有价值）。
2.现在，假设我们发现C [2,3]。它将为c [1,3] + D [1,2]。现在C [1,3]是指人    乙走访了0,2和3某甲维持在1或某乙走访了2,3和A    参观了0和1。此外，C [2,3]表示参观仅有2 / 0,1,2 / 0,2 / 1,2。因此，

Now, my problems are:
1. This solution has no definition for i=1 (as then k has no value).
2. Now, suppose we are finding c[2,3]. It would be c[1,3]+ d[1,2]. Now c[1,3] means person B visited 0, 2 and 3 and person A remained at 1 or person B visited 2 and 3 and A visited 0 and 1. Also, c[2,3] means A visited just 2/ 0,1,2 /0,2 /1,2. So,

 c[1,3] = min(d[0,1]+ d[2,3], d[0,2]+ d[2,3])
 c[2,3] = min(d[0,1]+ d[1,2], d[0,2]+ d[1,3], d[1,2]+d[0,3], d[0,1]+d[1,3])

如可以看到的解决方案不重叠。

As can be seen the solutions are not overlapping.

要把它在其他的方式，2已在C [1,3]包括经B。因此，如果我们包括C [1,3]在C [2,3]这将意味着，2是访问A和B这两者不是必需的，因为它只会增加成本。

To put it in other way, 2 is already covered by B in c[1,3]. So if we include c[1,3] in c[2,3] it would mean that 2 is visited by both A and B which is not required as it would just increase the cost.

请纠正我，如果我错了。

Please correct me if I am wrong.

推荐答案

问：::两个人穿越城市的序列：您将得到n个城市的有序序列，每对城市之间的距离。设计一个算法，以城市划分为两个子（不一定是连续的），使得某甲访问所有城市的第一个序列（按顺序），某乙访问所有城市在第二序列（按顺序），和的总和由A和B的总行驶距离最小化。最初假设某甲和某乙开始在各自的子序列的第一个城市。

Q:: Two-Person Traversal of a Sequence of Cities: You are given an ordered sequence of n cities, and the distances between every pair of cities. Design an algorithm to partition the cities into two subsequences (not necessarily contiguous) such that person A visits all cities in the first subsequence (in order), person B visits all cities in the second subsequence (in order), and the sum of the total distances travelled by A and B is minimised. Assume that person A and person B start initially at the first city in their respective subsequences.

下面是我理解的解决方案::

Here is how I understood the solution ::

让我们说的城市数量从1到n。我们对递归C（I，J），最小距离，如果一个人在城市结束我和某乙在城市Ĵ结束旅行。假设不失一般性我与其中的损失;学家

Let us say the cities are number from 1 to n. We recurse on C(i, j), the minimum distance traveled if person A ends at city i and person B ends at city j. Assume without loss of generality i < j.

让C（0，n）表示此人的不访问任何城市，而某乙来访[1，n]的所有城市。

Let C(0, n) denote that person A does not visit any city, while person B visits all the cities from [1, n].

因此​​，C（0，J）= D（1,2）+ D（2,3）+ ... + D（J-1，J）（B从城市1开始，打算为了钱柜城市J）

Hence, C(0, j) = d(1,2) + d(2,3) + .... + d(j-1, j) (B starting from city 1, going in order till city j).

C（I，J），其中i是不是0 =最小以下两种情况：

C(i, j), where i is not 0 = minimum of following two cases :

1的情况下：某甲启动和停止的城市我。在这种情况下，C（I，J）=距离由人物B行进，行进到所有城市从1到j，以便跳过城市I = D（1,2）+ D（2,3）+ ... D（I-1，I + 1）+δ（i + 1的，I + 2）+ ... + D（J-1，j）的

case 1 : person A starts and stops at city i. In which case, C(i, j) = distance travelled by person B, travelling to all cities from 1 to j in order, skipping city i = d(1,2) + d(2,3) + ... + d(i-1, i+1) + d(i+1, i+2) + ... + d(j-1, j)

2的情况下：某甲开始在一些城市之前，我，因此有他旅行之前去的城市我一个城市K（在他穿越倒数第二个城市）。在这种情况下，C（I，J）=最小{C（K，J）+ D（K，I）}其中k可以从1变化至i-1。

case 2 : person A starts at some city before i, and hence there is a city k which he travels just before going to city i (second last city in his traversal). In this case, C(i, j) = minimum {C(k, j) + d(k, i)} where k can vary from 1 to i-1.

的解决问题的方法是最小{C（I，N）}其中，i从0变化到n-1。

The solution to the problem is minimum { C(i,n) } where i varies from 0 to n-1.

我们可以填写行优先顺序DP矩阵，为C（I，J）的每个计算要求要么距离D，或C（K，J），其中K＆LT;一世。

We can fill the DP matrix in row major order, as each calculation of C(i,j) requires either the distances d, or C(k,j) where k < i.

该算法的运行时间将是为O（n ^ 3），因为有O（N ^ 2）项，我们做了计算，每次计算需要O（n）的时间。

The running time of the algorithm will be O(n^3), as there are O(n^2) entries for which we do the calculation, and each calculation takes O(n) time.

:我觉得在讲义中给出的解决方案是缺少案例1。

Edit :: I think the solution given in the handout is missing case1.

这篇关于动态规划：穿越城市的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！