algorithm - 动态规划 : traversal of cities

Question

我遇到了这个问题:

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

我寻找它的答案，答案是:
令 c[i,j] 为第一个人在城市 i 停留，第二个人在城市 j 停留时的最小行进距离。假设 i

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

解决方案也可以看问题10 here

现在，我的问题是:
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[1,3] 包含在 c[2,3] 中，则意味着 A 和 B 都访问了 2，这不是必需的，因为它只会增加成本。

如有错误请指正

Answer 1

Q::城市序列的两人遍历:给定一个由 n 个城市组成的有序序列，以及每对城市之间的距离。设计一个算法将城市划分为两个子序列(不一定连续)，使得 A 访问第一个子序列中的所有城市(按顺序)，B 访问第二个子序列中的所有城市(按顺序)，以及A 和 B 行进的总距离最小化。假设 A 和 B 最初从他们各自子序列中的第一个城市开始。

这是我对解决方案的理解:

假设城市是从 1 到 n 的数字。我们在 C(i, j) 上递归，如果 A 在城市 i 结束，B 在城市 j 结束，则旅行的最小距离。不失一般性地假设 i < j。

令 C(0, n) 表示 A 没有访问任何城市，而 B 访问了 [1, n] 中的所有城市。

因此，C(0, j) = d(1,2) + d(2,3) + .... + d(j-1, j) (B 从城市 1 开始，依次进行直到城市 j)。

C(i, j)，其中 i 不为 0 = 以下两种情况中的最小值:

情况 1:A 人在城市 i 开始和停止。在这种情况下，C(i, j) = 人 B 旅行的距离，按顺序从 1 到 j 旅行到所有城市，跳过城市 i = d(1,2) + d(2,3) + ... + d(i-1, i+1) + d(i+1, i+2) + ... + d(j-1, j)

情况 2:人 A 从 i 之前的某个城市开始，因此有一个城市 k，他在前往城市 i 之前经过了一个城市(他遍历的倒数第二个城市)。在这种情况下，C(i, j) = minimum {C(k, j) + d(k, i)} 其中 k 可以在 1 到 i-1 之间变化。

问题的解决方案是最小值 { C(i,n) } 其中 i 从 0 到 n-1 不等。

我们可以按行主要顺序填充 DP 矩阵，因为 C(i,j) 的每次计算都需要距离 d 或 C(k,j)，其中 k < i。

算法的运行时间为 O(n^3)，因为我们要计算 O(n^2) 个条目，而每次计算都需要 O(n) 时间。

编辑::我认为讲义中给出的解决方案缺少 case1。