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

【關鍵詞】動態(tài)規(guī)劃；旅行商；算法

二、動態(tài)規(guī)劃求解策略

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

（1） 找出最優(yōu)解的性質(zhì)，并刻畫其結構

（2） 遞歸定義最優(yōu)值的求解公式

（3） 以自底向上的方式計算最優(yōu)值

（4） 根據(jù)計算時得到的信息，構造一個最優(yōu)解

三、旅行商問題的動態(tài)規(guī)劃實現(xiàn)算法

用程序來模仿動態(tài)規(guī)劃算法，最重要的是一個分段過程，它與傳統(tǒng)算法的區(qū)別是“以自底向上的方式計算出最優(yōu)值”，我們以這一條準則分段。

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

private void guihua（int temp） {

if （list.size（） == 1） {

this.firnalRoad = list.get（0）；

this.min = this.store.get（list.get（0）） + ""；

return；

}

for （int i = 0； i < （list.size（） - 1）； i++） {

int next = （i + 1）；

if （list.get（i）.substring（0， temp

* this.lengthOfLength）.equals（list.get（next）.substring（0， temp * this.lengthOfLength））） {

double iValue = 0；

double nextValue = 0；

iValue = this.dArray[temp][Integer.parseInt（list.get（i）.substring（temp， temp + this.lengthOfLength））] +

store.get（list.get（i）.substring（（temp + 1）

* this.lengthOfLength））；

nextValue = this.dArray[temp][Integer.parseInt（list.get（next）.substring（

temp， temp + this.lengthOfLength））] +

store.get（list.get（next）.substring（（temp + 1）

* this.lengthOfLength））；

this.store.put（list.get（i）.substring（temp

* this.lengthOfLength）， iValue）；

this.store.put（list.get（next）.substring（

temp * this.lengthOfLength）， nextValue）；

if （iValue >= nextValue） {

list.remove（i）；

} else {

list.remove（next）；

}

i--；

}

}

this.guihua（temp - 1）；

}

4.測試實例

（1） first為{{0， 1， 2， 3}， {3， 0， 4， 6}， {4， 2， 0， 8}， {4， 3， 9， 0}}；

運行結果為：

路徑是：3201

城市順序：0->3->1->2->0

最小值：14.0

生成所有合法城市流用時：15毫秒

動態(tài)規(guī)劃求解過程用時：0毫秒

（2） first為{{0，2，1，3，4}， {1，0，4，4，2}， {5，4，0，2，2}， {5，2，2，0，3}， {4，2，4，2，0}}；

運行結果為：

路徑是：20413

城市順序：0->2->4->3->1->0

最小值：8.0

生成所有合法城市流用時：62毫秒

動態(tài)規(guī)劃求解過程用時：0毫秒

看第2個例子，輸出城市順序是“0->2->4->3->1->0”，由于我們是從0開始計數(shù)的，所以與上面數(shù)學計算中輸出的城市順序相同，并且最小值為8.0，也是正確的?？梢杂脭?shù)學計算方法驗證一下，以上例子的輸出都是正確的。

四、結束語

動態(tài)規(guī)劃法是一種有著廣泛應用的算法，它的優(yōu)越性在于省略了很多重復計算，所以在數(shù)學計算中應用較多。但隨著城市數(shù)量的增多，動態(tài)規(guī)劃算法求解問題的時間還是保持很大的增長率，所以動態(tài)規(guī)劃雖然提供了一種問題的求解辦法，但并不完美。

作者簡介

申永康（1997），男，漢族，山東日照，高中生，山東省日照一中。