穿越城市-这种情况是解决方案中缺少的吗？

Question

警告：这个问题需要一些初步的努力才能理解

这个问题并不完全是动态规划的重复：城市遍历。让我们假设我有以下4个城市的图表[0-3]：

  d[0][1] = 1;
  d[0][2] = 2;
  d[0][3] = 5;
  d[1][2] = 3;
  d[1][3] = 6;
  d[2][3] = 4;

链接中提出的解决方案是

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[1][2]：

c[1][2] = min between {
           k = 0 => C[0,1] + d[0][2]
          }

这很有意义，但这不是在这一步评估的唯一路径，因为我可以将城市[0，1]分组到第一个集合中，而将[2]单独放在第二个集合中。在这种情况下，它会是

c[1][2] = min between {
           k = 0 => C[0,1] + d[0][2]
           d[0][1]
          }

在这一点上，我想问我的反对是否有意义。如果确实如此，并且上面链接中提出的算法是错误的，我应该如何在解决方案中包含这种情况？我试图递归地表达它，但无法得出任何简单的东西。

Answer 1

您所指的解决方案确实是不完整的，并且没有考虑到第二个旅行者从< code>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
       and C[0,i]                        (if i = j-1)
}

这里的例外情况是C[0,1]，它应该设置为d[0,1]

通过这种方式，您还可以考虑第二个旅行者刚刚开始时的情况（C[0，i]将是第一个从0到i旅行的旅行者的成本，并且第二个旅行者从j = i 1开始没有费用）。

请注意，您也可以替换 0