天天看點

雙調旅行商問題 (Bitonic TSP)

問題描寫叙述:

雙調旅行商問題 (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的值。      
詳細實作稍後補充!!