雙調旅行商問題 (Bitonic TSP)

問題描寫叙述：

上述問題能夠使用動态規劃的方法來解決。

以下是解決思路的詳細介紹：

1. 最優子結構:

如果d[i][j]表示從起點1出發到達i及j兩個頂點的最短路程之和。      

為此能夠如果K為此段路程上與j相加的節點。則d[i][j] = d[i][k] + len[k][j]。

證明：若存在一個更短的路徑d[i][k]，則就應該存在更短的路徑d[i][j]。這與如果沖突，是以得證。

以下來尋找j相鄰的節點，當中若i<j-1，則顯然k=j-1,若i=j-1。則顯然k屬于(1,j-2)之間。為此得到例如以下的遞推關系：      

d[i][j] = d[i][j-1]+len(j,j-1) i<j-1;      

d[i][j] = min(d[i][k] + len(k,j)),k屬于(1,j-2)。      

終于輸出的d[n-1][n]就可以。      

對于路徑的輸出，僅僅須要記錄每次與j相鄰的節點就可以，也即記錄k的值。      

詳細實作稍後補充！！