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

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

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

動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。在這類問(wèn)題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，希望找到具有最優(yōu)解的那個(gè)解。一個(gè)動(dòng)態(tài)規(guī)劃算法通?？砂匆韵聨讉€(gè)步驟進(jìn)行：

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

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

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

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

三、旅行商問(wèn)題的動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)算法

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

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

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.測(cè)試實(shí)例

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

運(yùn)行結(jié)果為：

路徑是：3201

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

最小值：14.0

生成所有合法城市流用時(shí)：15毫秒

動(dòng)態(tài)規(guī)劃求解過(guò)程用時(shí)：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}}；

運(yùn)行結(jié)果為：

路徑是：20413

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

最小值：8.0

生成所有合法城市流用時(shí)：62毫秒

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

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

四、結(jié)束語(yǔ)

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

作者簡(jiǎn)介

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