城市遍歷 - 這個案例在解決方案中缺失了嗎？

Question

警告：這個問題，需要一些初步的努力來理解

這個問題是不完全的dynamic programming : traversal of cities重複。讓我們假設我有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

您提到的解決方案實際上是不完整的，並且不考慮第二旅行者從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 < k < i0 <= k < i，因爲k = 0導致C[0,i] + d[0,j]其中嚴格大於C[0,i]