但 開(kāi) 段隆振

(南昌大學(xué)信息工程學(xué)院 江西 南昌 330031)

0 引 言

經(jīng)典的旅行商問(wèn)題(Travelling Salesman Problem,TSP)可以描述為：給定一組城市,這些城市之間的距離已知,尋找一條經(jīng)過(guò)所有城市一次且僅一次并返回起始城市的最短路線。旅行商問(wèn)題有著廣泛的實(shí)際應(yīng)用,生活中經(jīng)常出現(xiàn)的各類(lèi)組合優(yōu)化問(wèn)題都可以歸為旅行商這類(lèi)問(wèn)題。如物資運(yùn)輸路線中,汽車(chē)應(yīng)走怎樣的路線使路程最短[1]；大型工業(yè)制件在增材制造中的路徑規(guī)劃[2]；CNC在線檢測(cè)中,如何盡可能縮短檢測(cè)路徑長(zhǎng)度[3]；在航海相關(guān)問(wèn)題中,無(wú)人駕駛船舶路徑規(guī)劃或船舶航線自動(dòng)生成[4]；多無(wú)人機(jī)協(xié)同作業(yè)中,規(guī)劃出符合無(wú)人機(jī)機(jī)動(dòng)性能約束和安全要求的最優(yōu)航跡的問(wèn)題[5]等。

三角不等式是TSP的一個(gè)很自然的限制：對(duì)任意三座城市A、B和C,從A到C的路程加上從C到B的路程應(yīng)該大于等于從A到B的路程。旅行成本是對(duì)稱(chēng)的,而且滿足三角不等式的題目稱(chēng)為T(mén)SP的度量(metric)題目。當(dāng)把城市視為平面上的點(diǎn),許多距離計(jì)算方式都滿足這個(gè)自然條件,例如城市距離為歐幾里得距離(Euclidean distance)、曼哈頓距離(Manhattan distance)、切比雪夫距離(Chebyshev distance)的TSP都屬此類(lèi)。如果兩個(gè)城市之間的距離是相應(yīng)的歐幾里得距離,且兩個(gè)城市之間的距離在兩個(gè)方向上都是相同的,這樣的TSP稱(chēng)為對(duì)稱(chēng)的Euclidean TSP。許多自然實(shí)例都是對(duì)稱(chēng)的Euclidean TSP。

旅行商問(wèn)題的最優(yōu)化求解非常困難,其最根本的原因是求解這些問(wèn)題的現(xiàn)有算法需要極長(zhǎng)的運(yùn)行時(shí)間以及極大的存儲(chǔ)空間,以至于根本不可能在現(xiàn)有的計(jì)算機(jī)上實(shí)現(xiàn),即存在所謂的“組合爆炸”。例如31個(gè)城市的旅行商問(wèn)題,使用窮舉法需要遍歷30!/2種排列。如果使用目前我國(guó)排名第一的超級(jí)計(jì)算機(jī)——神威太湖之光(Sunway TaihuLight,含有10 649 600個(gè)處理器,運(yùn)算速度可達(dá)每秒125 436萬(wàn)億次),假設(shè)檢驗(yàn)每條路線只需要一次算術(shù)運(yùn)算,那么解決這道31個(gè)城市的TSP問(wèn)題預(yù)計(jì)需要超過(guò)3 352萬(wàn)年。

通過(guò)Cook[6]和Karp[7]的理論,可以將旅行商問(wèn)題和許多其他問(wèn)題聯(lián)系起來(lái)。很多的組合優(yōu)化問(wèn)題,比如背包問(wèn)題、車(chē)間調(diào)度問(wèn)題、分配問(wèn)題都和旅行商問(wèn)題同屬于NP完全問(wèn)題。如果其中任意一個(gè)能用多項(xiàng)式確定性算法解決,那么其他所有NP完全問(wèn)題也能用多項(xiàng)式算法解決。事實(shí)上,有很多方法本來(lái)是研究旅行商問(wèn)題時(shí)提出來(lái)的,經(jīng)過(guò)不斷的發(fā)展,后來(lái)又推廣到了其他NP完全問(wèn)題上去。

動(dòng)態(tài)規(guī)劃(Dynamic Programming)是解決多階段決策過(guò)程最優(yōu)化的一種數(shù)學(xué)方法。在多階段決策過(guò)程中,動(dòng)態(tài)規(guī)劃方法將問(wèn)題的過(guò)程分成幾個(gè)相互聯(lián)系的階段,恰當(dāng)?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù),從而把一個(gè)大問(wèn)題化成一組同類(lèi)型的子問(wèn)題,然后逐個(gè)求解。即從邊界條件開(kāi)始,逐段遞推尋優(yōu),在每一個(gè)子問(wèn)題的求解中,均利用了它前面的子問(wèn)題的最優(yōu)化結(jié)果,依次進(jìn)行,最后一個(gè)子問(wèn)題所得的最優(yōu)解,就是整個(gè)問(wèn)題的最優(yōu)解。動(dòng)態(tài)規(guī)劃的方法在電網(wǎng)調(diào)峰[8]、航天航空[9]和保險(xiǎn)金融[10]等領(lǐng)域中都有廣泛的應(yīng)用。

已知求解旅行商問(wèn)題的精確算法的運(yùn)行時(shí)間界限是Held-Karp[11]動(dòng)態(tài)規(guī)劃法的O(n22n),這個(gè)紀(jì)錄已經(jīng)保持了58年。如果能突破這個(gè)界限,哪怕只是一點(diǎn)點(diǎn)改進(jìn),也有可能獲得更快的時(shí)間界限,就有可能適用于實(shí)際應(yīng)用,從而推進(jìn)旅行商問(wèn)題的實(shí)戰(zhàn)前線。

1 簡(jiǎn)單插入與兩個(gè)猜想

1.1 簡(jiǎn)單插入

插入算法(Insertion Algorithm)的思路是從一條周游幾個(gè)城市的子路線出發(fā),逐個(gè)增加新的城市并插入到合適位置,直至得到一條包含所有城市的新路線。算法核心部分的偽代碼為：

Begin

設(shè)算法運(yùn)行過(guò)程中M為當(dāng)前子路線；

根據(jù)新城市選取函數(shù)選取待插入城市i；

根據(jù)插入位點(diǎn)選取函數(shù)選取插入位點(diǎn)p；

M.insert(p,i)；

if所有城市均在M中：

返回M；

else：

進(jìn)行下一步插入操作；

End

其中插入位點(diǎn)選取的規(guī)則是遍歷所有可插入位點(diǎn),計(jì)算插入后的路線長(zhǎng)度,其中最短路線長(zhǎng)度所對(duì)應(yīng)的位點(diǎn)作為插入位點(diǎn)。將這條規(guī)則稱(chēng)作簡(jiǎn)單選取規(guī)則,通過(guò)簡(jiǎn)單選取規(guī)則進(jìn)行的插入稱(chēng)為簡(jiǎn)單插入。

1.2 一個(gè)插入法的實(shí)例

例1十三個(gè)城市的TSP,城市從0到12依次編號(hào),城市橫坐標(biāo)依次為{466,826,555,79,781,251,329,336,978,793,489,496,735},城市縱坐標(biāo)依次為{407,389,485,264,618,766,640,670,195,15,714,218,438}。

其最優(yōu)路線為[7,6,2,0,3,11,9,8,1,12,4,10,5],最優(yōu)路線長(zhǎng)為3 082個(gè)單位長(zhǎng)度,如圖1所示。

圖1 例1的最優(yōu)路線

對(duì)于旅行商問(wèn)題,有兩個(gè)最基本定理,分別是交叉避免和凸包規(guī)則。

交叉避免：最優(yōu)路線不會(huì)自交,因此在解題過(guò)程中應(yīng)避免出現(xiàn)交叉的情況。

用一步2-opt可以證明這個(gè)事實(shí),若巡回路徑中存在交叉路徑,則打開(kāi)交叉路徑得到的路徑長(zhǎng)度一定小于原路徑長(zhǎng)度。

凸包規(guī)則：最優(yōu)路線中經(jīng)過(guò)邊界各點(diǎn)的順序和凸包邊界經(jīng)過(guò)邊界各點(diǎn)的順序相同。它們?cè)谶吔缟系捻樞蚺c在最優(yōu)路線上的順序相同,其余城市的順序則是由邊界向內(nèi)側(cè)拐入短的子路徑而得。

最優(yōu)路線需要避免自交,所以經(jīng)過(guò)邊界各點(diǎn)的順序必須和凸包邊界經(jīng)過(guò)邊界各點(diǎn)的順序相同。

對(duì)于例1,使用凸核插入法,即初始子路線從城市點(diǎn)集的凸包開(kāi)始,插入位點(diǎn)選取規(guī)則不變,遍歷所有可能的插入順序,可能得到的結(jié)果只有4種,如圖2所示。其中路線長(zhǎng)度最小為3 106個(gè)單位長(zhǎng)度,大于最優(yōu)路線的3 082個(gè)單位長(zhǎng)度。

圖2 凸核插入法求解例1的所有可能結(jié)果

作為近似算法而言,在插入法中加入能夠把握整體形狀的初始子路線可以在插入城市的過(guò)程不斷完善細(xì)節(jié),往往能得到比不加入初始子路線更優(yōu)質(zhì)的路線。但在尋找最優(yōu)解方面,由于插入法在插入過(guò)程中不會(huì)改變已插入的城市排列,所以加入的初始子路線首先必須保證其排列與其在最優(yōu)路線上的排列一致。即使找到凸包這種特殊的初始子路線滿足排列一致的條件,例1也說(shuō)明了其有可能無(wú)法達(dá)到最優(yōu)解。

1.3 簡(jiǎn)單插入最優(yōu)性猜想

例1已經(jīng)指出增加初始子路線的做法會(huì)使得最優(yōu)解被排除在算法的解空間之外,那么,不指定初始子路線,用簡(jiǎn)單插入的方式,遍歷所有的城市插入順序,是否必定能得到最優(yōu)解呢？對(duì)于例1,按照插入順序5→10→4→12→11→1→8→6→2→0→9→3→7,可以得到最優(yōu)解,如圖3所示。

圖3 不指定初始子路線基于簡(jiǎn)單插入的例1最優(yōu)解插入過(guò)程

針對(duì)對(duì)稱(chēng)的Euclidean TSP,考慮如下猜想。

簡(jiǎn)單插入最優(yōu)性猜想：對(duì)于任意TSP,依據(jù)簡(jiǎn)單選取規(guī)則的插入法的所有可能中,必定包括TSP的最優(yōu)解。

1.4 插入過(guò)程與插座

定義1對(duì)于任意的TSP,從其最優(yōu)路線中選擇任一城市a剔除,剩下的城市排列為城市a的插座。

定理1通過(guò)將a簡(jiǎn)單插入a的插座中得到的必定是最優(yōu)路線。

證明：用反證法。

若將a簡(jiǎn)單插入a的插座中得到的不是最優(yōu)路線,設(shè)a插入的位點(diǎn)為i,最優(yōu)路線中a的插入位點(diǎn)為j,根據(jù)簡(jiǎn)單插入的定義,有插入i后的路線長(zhǎng)度tour(i)小于插入j后的路線長(zhǎng)度tour(j),這與最優(yōu)路徑長(zhǎng)度最短的定義矛盾。證畢。

插座本身可以看作原問(wèn)題規(guī)模減一的TSP,如果插座中的城市排列恰好是這個(gè)子問(wèn)題的最優(yōu)解,這樣的插座稱(chēng)為同型插座,其他的不是子問(wèn)題最優(yōu)解的則稱(chēng)為異型插座。城市數(shù)量為n的TSP,插座總數(shù)為n。

1.5 同型插座猜想

易知,存在異型插座數(shù)量為0情形(n個(gè)城市的凸包),那么存在同型插座數(shù)量為0的情形嗎？

針對(duì)對(duì)稱(chēng)的Euclidean TSP,考慮如下猜想。

同型插座猜想：對(duì)于任意TSP,必然存在同型插座。

根據(jù)定理1,對(duì)于任意TSP,其最優(yōu)解可以由其中一個(gè)城市通過(guò)簡(jiǎn)單插入操作插入到與其對(duì)應(yīng)的插座中得到。而根據(jù)同型插座猜想,對(duì)于任意TSP,必然存在同型插座,同型插座即為子集的最優(yōu)解。結(jié)合定理1以及同型插座猜想,由數(shù)學(xué)歸納法即可推出下面的同型插座猜想的推論。

同型插座猜想的推論：對(duì)于任意TSP,依據(jù)簡(jiǎn)單選取規(guī)則,必然存在這樣插入過(guò)程：插入中每一步的子路線都是當(dāng)前的TSP最優(yōu)解。

這樣的插入過(guò)程中可以根據(jù)子路線中不同城市的數(shù)量分為n個(gè)階段,每個(gè)階段所有子路線的集合稱(chēng)為該階段的最優(yōu)插入子集。

圖3中的插入過(guò)程就是這一推論的一個(gè)例子,在每一步的插入過(guò)程中,其插入后形成的路線都是當(dāng)前已插入城市組成的子問(wèn)題的最優(yōu)解。

1.6 同型插座數(shù)量分布規(guī)律的統(tǒng)計(jì)分析

在1 000×1 000正方形區(qū)域內(nèi)隨機(jī)取m個(gè)點(diǎn)的坐標(biāo)數(shù)據(jù),這些數(shù)據(jù)構(gòu)成了城市規(guī)模為m的旅行商問(wèn)題,用X表示這個(gè)旅行商問(wèn)題的同型插座數(shù)量,X是一個(gè)隨機(jī)變量,它的概率密度記為f(x),其均值為μ,標(biāo)準(zhǔn)差為σ。設(shè)X1,X2,…,Xn表示來(lái)自f(x)的一列獨(dú)立的隨機(jī)變量。根據(jù)中心極限定理,當(dāng)n很大時(shí)(在實(shí)際的抽樣中,一般當(dāng)樣本容量大于等于30時(shí)就可以應(yīng)用中心極限定理),隨機(jī)變量Yn近似地服從正態(tài)分布N(nμ,nσ2)。

已知Yn的概率分布模型,可以利用樣本的密度構(gòu)造似然函數(shù)求出μ和σ2的極大似然估計(jì)值。Yn的似然函數(shù)為：

(1)

對(duì)式(1)兩邊取對(duì)數(shù)：

(2)

對(duì)式(2)求偏導(dǎo)：

解得：

考慮一般情況,假設(shè)城市個(gè)數(shù)為n的所有TSP組成一個(gè)集合Un,用Cm表示Un中異型插座的數(shù)量為m個(gè)的所有元素集合,m=0,1,…,n。如果同型插座猜想成立,那么對(duì)于任意Un,可知Cn=??？紤]三個(gè)城市的TSP,其所有排列方式都是等價(jià)的,換言之,三個(gè)城市的TSP只有一條路線,這條路線即為最佳路線。根據(jù)插座理論可知,四個(gè)城市的TSP有四個(gè)插座,這些插座都是三個(gè)城市,又因?yàn)槿齻€(gè)城市只有一種可能路線(即最佳路線),所以四個(gè)插座皆為同型插座。如果同型插座猜想不成立,則存在城市個(gè)數(shù)為k的TSP不存在同型插座。綜上所述,k應(yīng)該大于等于5。

表1 插座型號(hào)數(shù)量分布實(shí)驗(yàn)的數(shù)據(jù)

從表1同型插座數(shù)量頻數(shù)分布的實(shí)驗(yàn)數(shù)據(jù)中可以看出,同型插座為1的情形,在城市數(shù)量大于7時(shí)開(kāi)始出現(xiàn),且不同城市數(shù)量的3萬(wàn)次獨(dú)立實(shí)驗(yàn)中出現(xiàn)的頻數(shù)均為個(gè)位數(shù),計(jì)算其平均頻率為0.000 103；同型插座為0的情形,在實(shí)驗(yàn)中沒(méi)有出現(xiàn)過(guò)一次。這樣的實(shí)驗(yàn)結(jié)果有兩種可能：(1) 同型插座猜想成立,任意TSP至少存在一個(gè)同型插座；(2) 存在同型插座猜想的反例,即存在同型插座數(shù)量為0的TSP,但反例的出現(xiàn)是極小概率的事件,以至于在本次實(shí)驗(yàn)中未出現(xiàn)。

假設(shè)同型插座猜想存在反例。根據(jù)伯努利大數(shù)定律,當(dāng)n足夠大時(shí),事件A出現(xiàn)的頻率將接近于其發(fā)生的概率。比如同型插座數(shù)量為1的情形,用頻率估計(jì)其概率,概率約為萬(wàn)分之一。同型插座數(shù)量為0的情形,頻率為0,根據(jù)假設(shè)其概率不為0,那么,其概率必然遠(yuǎn)小于萬(wàn)分之一。

從圖4中可以看出,同型插座的分布形態(tài)隨著城市個(gè)數(shù)的增加,越來(lái)越接近兩邊少、中間多的鐘形分布概率模型。在典型的鐘形分布即正態(tài)分布中,如果a小于標(biāo)準(zhǔn)差μ,那么P{x

圖4 同型插座的頻數(shù)分布

如果考慮同型插座數(shù)量小于4的情形,從圖5中可以看到隨著城市個(gè)數(shù)的增加,其出現(xiàn)的次數(shù)是遞減的,這意味著隨著問(wèn)題規(guī)模增加,同型插座數(shù)量小于4出現(xiàn)的概率在下降。

圖5 同型插座數(shù)量小于4的頻數(shù)隨城市規(guī)模的變化

綜上所述,同型插座猜想的反例即使存在,也是小概率事件,而且隨著城市規(guī)模越大,這個(gè)概率呈減小的趨勢(shì)。

2 算法設(shè)計(jì)與實(shí)現(xiàn)

2.1 基于簡(jiǎn)單插入子集的動(dòng)態(tài)規(guī)劃法

考慮n座城市的TSP題目,城市從1到n依次編號(hào)命名。依據(jù)簡(jiǎn)單插入子集中的城市數(shù)量可以劃分為不同的階段,用k表示,k分別等于1,2,…,n。

以城市集{1,2,3,4,5}為例,城市數(shù)量為3的子集有{1,2,3}、{1,2,4}、{1,2,5}、{1,3,4}、{1,3,5}、{1,4,5}、{2,3,4}、{2,3,5}、{2,4,5}、{3,4,5}共10個(gè),因?yàn)槿齻€(gè)城市的路線實(shí)際只有一條,這里每一個(gè)城市子集對(duì)應(yīng)一個(gè)子路線,所以第三階段有10個(gè)狀態(tài)。

其城市數(shù)量為4的子集有{1,2,3,4}、{1,2,3,5}、{1,2,4,5}、{1,3,4,5}、{2,3,4,5}共5個(gè)。其中{1,2,3,4}可由{1,2,3}插入4、{1,2,4}插入3、{1,3,4}插入2、{2,3,4}插入1這四種情況得到相應(yīng)的簡(jiǎn)單插入子路線,這四條路線有可能重復(fù),記錄下不同的成為第四階段的一個(gè)狀態(tài)。一般第四階段以后,每個(gè)城市子集都有可能對(duì)應(yīng)多個(gè)子路線,至少為一個(gè),且不同題目對(duì)應(yīng)不同的數(shù)量。

第五階段的城市子集為{1,2,3,4,5},可由{1,2,3,4}插入5、{1,2,3,5}插入4、{1,2,4,5}插入3、{1,3,4,5}插入2、{2,3,4,5}插入1得到。以{1,2,3,4}插入5的情況為例,在第四階段找到城市子集{1,2,3,4}對(duì)應(yīng)的簡(jiǎn)單插入子路線,假如有a條子路線,那么就將城市5逐個(gè)插入其中,記錄下不重復(fù)的新的子路線。

在最后一個(gè)階段的狀態(tài)轉(zhuǎn)移完成后,會(huì)得到{1,2,3,4,5}所對(duì)應(yīng)的多條簡(jiǎn)單插入子路線,根據(jù)簡(jiǎn)單插入最優(yōu)性猜想,最優(yōu)解必在其中,此時(shí)只要計(jì)算這些路線的長(zhǎng)度,最短的那條即為該旅行商問(wèn)題的最短旅行路線。

2.2 基于最優(yōu)插入子集的新動(dòng)態(tài)規(guī)劃法

依據(jù)同型插座猜想的推論,TSP的最優(yōu)解可以通過(guò)同型插座進(jìn)行簡(jiǎn)單插入得到,城市個(gè)數(shù)為n的TSP有n個(gè)插座,這些插座可能為同型,也可能為異型。同型插座猜想指出這n個(gè)插座中必然存在一個(gè)同型插座。n個(gè)插座對(duì)應(yīng)n個(gè)TSP的子問(wèn)題,這些城市個(gè)數(shù)為n的TSP都有最優(yōu)解,它們與插座的關(guān)系是,同型插座等價(jià)于子問(wèn)題的最優(yōu)解,異型插座不是子問(wèn)題的最優(yōu)解。

假設(shè)我們知道所有城市個(gè)數(shù)為n的子問(wèn)題的最優(yōu)解,那么這些最優(yōu)解中必然至少有一個(gè)會(huì)是原問(wèn)題的同型插座,對(duì)所有這些最優(yōu)解進(jìn)行簡(jiǎn)單插入,假設(shè)a為插入城市,那么可能的結(jié)果只有兩種,(1) (城市a)+(a的同型插座)=最優(yōu)解；(2) (城市a)+(非插座)=非最優(yōu)解,由前文得知第一種結(jié)果必定存在,因此可以遍歷所有結(jié)果,其中路線長(zhǎng)度最小的即為最優(yōu)解。同時(shí),城市個(gè)數(shù)為n-1的子問(wèn)題的最優(yōu)解可以如法炮制,從城市個(gè)數(shù)為n-2的子問(wèn)題中得到,即滿足無(wú)后效性(馬爾可夫性)。因此,可以從城市個(gè)數(shù)為3(3個(gè)城市無(wú)須排列即為最優(yōu)路線)開(kāi)始,逐步求得城市個(gè)數(shù)為4,5,…，n的最優(yōu)解。

根據(jù)同型插座猜想的推論,必然存在這樣插入過(guò)程：插入中每一步的子集都是當(dāng)前的TSP最優(yōu)解,這樣的子集稱(chēng)為最優(yōu)插入子集。這是簡(jiǎn)單插入最優(yōu)性猜想的一個(gè)特例。與基于簡(jiǎn)單插入子集的動(dòng)態(tài)規(guī)劃法相比,新動(dòng)態(tài)規(guī)劃法只需關(guān)注簡(jiǎn)單插入子集中最優(yōu)的部分,有效減少了每個(gè)階段的狀態(tài)數(shù)量,因此,算法的效率得到了提升。

城市個(gè)數(shù)為n的TSP,共有2n個(gè)子集(包括它自己和空集,事實(shí)上算法是從城市數(shù)目為3的子集開(kāi)始的,為方便計(jì)算,此處增加到最大值2n),在每一個(gè)子集中,至多有n個(gè)插座,對(duì)每一個(gè)插座,主要操作為復(fù)雜度為n的簡(jiǎn)單插入。2n乘以n再乘以n,所以新動(dòng)態(tài)規(guī)劃法的時(shí)間復(fù)雜度為O(n22n)。

由于動(dòng)態(tài)規(guī)劃法本身存在的“維數(shù)障礙”,在電子計(jì)算機(jī)上計(jì)算時(shí),每遞推一段,都必須把前一段算出的最優(yōu)值函數(shù)在相應(yīng)的狀態(tài)集合上的全部值存入內(nèi)存中,因而當(dāng)維數(shù)增大時(shí),所需的內(nèi)存量會(huì)呈指數(shù)倍增長(zhǎng)。在新動(dòng)態(tài)規(guī)劃法中,每一個(gè)城市子集都對(duì)應(yīng)一個(gè)狀態(tài),一共有2n個(gè)城市子集,每個(gè)城市子集最多有n個(gè)城市,因此空間復(fù)雜度為O(n2n)。

2.3 算法實(shí)現(xiàn)

算法運(yùn)行的硬件環(huán)境為Intel Core i5- 3320M CPU,2.6 GHz,4 GB內(nèi)存,開(kāi)發(fā)環(huán)境為Python 3.7。實(shí)驗(yàn)采用TSPLIB上的不同數(shù)據(jù)集,驗(yàn)證算法在各種潛在樣本上的有效性。實(shí)驗(yàn)采用了eg7146、kz9976、mo14185、xqg237和xql662的實(shí)驗(yàn)數(shù)據(jù),每次實(shí)驗(yàn)隨機(jī)選擇數(shù)據(jù)集中的12個(gè)城市,用Held-Karp動(dòng)態(tài)規(guī)劃法(HK),基于簡(jiǎn)單插入子集的動(dòng)態(tài)規(guī)劃法(簡(jiǎn)插法),基于最優(yōu)插入子集的動(dòng)態(tài)規(guī)劃法(優(yōu)插法)計(jì)算得到結(jié)果,表2是一次實(shí)驗(yàn)的數(shù)據(jù)。

表2 在不同數(shù)據(jù)集上的一次實(shí)驗(yàn)結(jié)果

這樣的實(shí)驗(yàn)重復(fù)進(jìn)行一萬(wàn)次,實(shí)驗(yàn)結(jié)果解異同均為T(mén)RUE,即三種算法的解都是最優(yōu)解。這初步表明在不同數(shù)據(jù)集中,基于最優(yōu)插入子集的動(dòng)態(tài)規(guī)劃法能有效求得最優(yōu)解。

3 結(jié) 語(yǔ)

基于簡(jiǎn)單插入子集的動(dòng)態(tài)規(guī)劃法的理論依據(jù)是簡(jiǎn)單插入最優(yōu)性猜想。這一猜想理論上的證明或許能帶來(lái)對(duì)TSP結(jié)構(gòu)上的深入認(rèn)識(shí)。

基于最優(yōu)插入子集的動(dòng)態(tài)規(guī)劃法的理論依據(jù)是同型插座猜想。對(duì)于同型插座猜想,實(shí)驗(yàn)測(cè)試的統(tǒng)計(jì)分析表明它有可能存在反例,但是即使存在反例,其在實(shí)際情況中出現(xiàn)的概率極小。而且城市規(guī)模越大,反例出現(xiàn)的概率越接近0。

如果無(wú)數(shù)多的猴子在無(wú)數(shù)多的打字機(jī)上隨機(jī)地打字,并持續(xù)無(wú)限久的時(shí)間,那么在某個(gè)時(shí)候,它們必然會(huì)打出莎士比亞的全部著作。這個(gè)設(shè)想本身在現(xiàn)實(shí)生活中是不可能重現(xiàn)的,就像一個(gè)房間內(nèi)的空氣總是均勻分布的。同型插座猜想可能也有類(lèi)似的性質(zhì),理論上存在反例,但實(shí)際遇到的TSP都滿足同型插座猜想。算法實(shí)現(xiàn)中采用了TSPLIB上的不同數(shù)據(jù)集,基于最優(yōu)插入子集的動(dòng)態(tài)規(guī)劃法均能找到最優(yōu)解,實(shí)驗(yàn)結(jié)果在一定程度上支持了這種觀點(diǎn)。

新動(dòng)態(tài)規(guī)劃算法為求解旅行商問(wèn)題提供了新的思路,對(duì)于認(rèn)識(shí)、分析眾多復(fù)雜問(wèn)題具有一定的啟示,對(duì)促進(jìn)組合優(yōu)化問(wèn)題的研究有著積極的作用。如果將其與其他啟發(fā)式算法融合或許會(huì)催生出性能優(yōu)異的新算法,這將給實(shí)際解決大規(guī)模TSP問(wèn)題提供新的方案。