3

我遇到了这个问题：

有两个人。有n个城市的有序序列，每对城市之间的距离是给定的。您必须将城市划分为两个子序列（不一定是连续的），使得 A 人访问第一个子序列中的所有城市（按顺序），人 B 访问第二个子序列中的所有城市（按顺序），并且使得A 和 B 的总距离最小化。假设人 A 和人 B 最初从他们各自子序列中的第一个城市开始。

我寻找它的答案，答案是：
让 c[i,j] 是如果第一个人停在城市 i 和第二个人停在城市 j 的最短距离。假设 i< j

c[0,j]= k 从 1 到 j-1 的 (d[k,k+1]) 之和
c[i,j] = min(c[k,j]+ d[k,i])如果 i!=0 其中 0

解决方案也可以在这里的问题 10 中看到

现在，我的问题是：
1. 这个解决方案没有 i=1 的定义（因为 k 没有价值）。
2. 现在，假设我们正在寻找 c[2,3]。它将是 c[1,3]+ d[1,2]。现在 c[1,3] 表示 B 访问了 0、2 和 3，而 A 保持在 1 或 B 访问了 2 和 3，A 访问了 0 和 1。此外，c[2,3] 表示 A 仅访问了 2/ 0,1,2 /0,2 /1,2。所以，

 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])

可以看出，解决方案没有重叠。

换句话说，2 已经被 c[1,3] 中的 B 覆盖。因此，如果我们在 c[2,3] 中包含 c[1,3]，则意味着 A 和 B 都访问了 2，这不是必需的，因为它只会增加成本。

如果我错了，请纠正我。

4

2 回答 2

2

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 ::

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.

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

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), where i is not 0 = minimum of following two cases :

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)

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.

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

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.

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.

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

于 2013-11-04T10:23:04.363 回答
1

您说得对，建议的解决方案有些混乱且不正确。

思考问题的方法一如既往地归纳：如果我需要解决大小为 n 的问题，我如何将其简化为更小的问题（0，...，n-1）。如果您想解决大小为 n 的问题，请注意其中一名玩家需要将节点 n 带入他们的路径。

C[i, j] 函数是一个辅助函数，表示如您所描述的“A 停在 i 和 B 停在 j 的最小成本”。

为了到达状态 C[i,j]，玩家 B 必须从 j-1 到 j，当然除非 j-1 = i。在 j-1 = i 的情况下，j 必须来自某个 k < i。因此函数 C[i, j] 可以描述如下：

C[i,j] = {
   C[i,j-1] + d[j-1,j]                   (if i < j-1)
   min C[k,i] + d[k,j] for 0 <= k < i    (if i = j-1)
}

使用此设置，您的基本情况就是 C[0, 1] = d[0,1]。

那么你的最终答案是 min C[k, n] for 0 <= k < n。

于 2012-12-17T17:06:59.310 回答