动态规划:穿越城市

Question

我遇到了这个问题：

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

我寻找它的答案，答案是:< br >假设c[i，j]是第一个人在城市I停留，第二个人在城市j停留时的最小行驶距离。假设I

c[0，j]= 从 1 到 j-1 的 k 的 （d[k，k1]） 之和
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[1，3]包含在c[2，3]中，这将意味着A和B都访问了2，这不是必需的，因为这只会增加成本。

如果我错了，请纠正我。

Answer 1

你是对的，建议的解决方案有些混乱和不正确。

像往常一样，思考问题的方法是归纳的：如果我需要解决大小n的问题，我如何将其简化为更小的问题（0，…，n-1）。如果你想解决大小n的问题，你注意到其中一个玩家需要将节点n带入他们的路径。

C[i，j]函数是一个helper函数，表示您所描述的“a在i处停止，B在j处停止时的最小成本”。

为了达到C[i，j]状态，参与人B必须从j-1到j，除非j-1 = i，在j-1 = i的情况下，j必须从k开始

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

你的最终答案是0的最小C[k， n]

Answer 2

问：：一个城市序列的两人遍历：您将获得一个由 n 个城市组成的有序序列，以及每对城市之间的距离。设计一种算法将城市划分为两个子序列（不一定是连续的），以便人员 A 访问第一个子序列中的所有城市（按顺序），人员 B 访问第二个子序列中的所有城市（按顺序），并且最小化 A 和 B 行进的总距离之和。假设人员 A 和人员 B 最初从其各自子序列中的第一个城市开始。

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

让我们假设城市是从1到n的数字。我们在C（i，j）上递归，如果人A结束于城市i，人B结束于城市j，则最小行驶距离。假设不损失一般性i

设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。

问题的解是minimum { C(i，n) }其中I从0变化到n-1。

我们可以按行的主要顺序填充DP矩阵，因为C（i， j）的每次计算都需要距离d或k所在的C（k， j）

算法的运行时间为O（n^3），因为我们为O（n^2）个条目进行计算，并且每次计算花费O（n）时间。

编辑 ：： 我认为讲义中给出的解决方案缺少案例1。