使用動態規劃解決旅行商問題

【摘要】旅行商問題是指給定一組城市和道路，求一條從指定城市出發、通過所有其它城市一次、再返回出發城市的代價最小的路徑。旅行商問題是一個經典的NP完全問題，其傳統的求解算法為窮舉法，按所有可能的路徑計算一遍，比較所有的計算結果，選擇其中的最短路徑。

【關鍵詞】動態規劃；旅行商；算法

二、動態規劃求解策略

動態規劃算法通常用于求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，希望找到具有最優解的那個解。一個動態規劃算法通常可按以下幾個步驟進行：

（1） 找出最優解的性質，并刻畫其結構

（2） 遞歸定義最優值的求解公式

（3） 以自底向上的方式計算最優值

（4） 根據計算時得到的信息，構造一個最優解

三、旅行商問題的動態規劃實現算法

用程序來模仿動態規劃算法，最重要的是一個分段過程，它與傳統算法的區別是“以自底向上的方式計算出最優值”，我們以這一條準則分段。

在第一次遍歷所有的城市流時，每相鄰的兩個城市流，前三個字符相同的，我們判斷一下最后兩個字符決定的路徑長度，刪除路徑較長的城市流，保存路徑較短的城市流，由于刪除了一個城市流，所以我們需要從當前的城市流重新比較一次（反映在一個循環中，就應該是當前的index減1）。當然，在這個比較過程中，我們把計算出的每一個長度都保存起來，這樣，我就能避免很多重復計算，這也正是使用動態規劃的益處！……