數(shù)學建模經(jīng)典問題-旅行商問題

關于數(shù)學建模經(jīng)典問題——旅行商問題第一頁，共一百零五頁，編輯于2023年，星期一2第7章旅行商問題1.問題概述

2.求解算法

2.1.下界和上界算法2.2.分支定界法

目錄2.5.競賽題2.3.動態(tài)規(guī)劃法2.5.近似算法第二頁，共一百零五頁，編輯于2023年，星期一3§7-1問題概述

一、數(shù)學模型

1.標準TSP

旅行商問題（簡稱TSP），也稱貨郎擔問題或旅行推銷員問題，是運籌學中一個著名的問題，其一般提法為：有一個旅行商從城市1出發(fā)，需要到城市2、3、…、n去推銷貨物，最后返回城市1，若任意兩個城市間的距離已知，則該旅行商應如何選擇其最佳行走路線？第三頁，共一百零五頁，編輯于2023年，星期一4TSP在圖論意義下又常常被稱為最小Hamilton圈問題，Euler等人最早研究了該問題的雛形，后來由英國的Hamilton爵士作為一個懸賞問題而提出。但這個能讓普通人在幾分鐘內(nèi)就可理解的游戲之作，卻延續(xù)至今仍未能完全解決，成了一個世界難題。

TSP有著明顯的實際意義，如，郵局里負責到各信箱開箱取信的郵遞員，以及去各分局送郵件的汽車等，都會遇到類似的問題。有趣的是，還有一些問題表面上看似乎與TSP無關，而實質(zhì)上卻可以歸結為TSP來求解。已經(jīng)證明，TSP是個NP難題，除非P=NP，否則不存在有效算法。第四頁，共一百零五頁，編輯于2023年，星期一5

記為賦權圖G=(V,E)，V為頂點集，E為邊集，各頂點間的距離dij已知。設則經(jīng)典的TSP可寫為如下的數(shù)學規(guī)劃模型：第五頁，共一百零五頁，編輯于2023年，星期一6

模型中，為集合中所含圖的頂點數(shù)。約束（7－1）和（7－2）意味著對每個點而言，僅有一條邊進和一條邊出；約束（7－3）則保證了沒有任何子回路解的產(chǎn)生。于是，滿足約束（7－1）、（7－2）和（7－3）的解構成了一條Hamilton回路。第六頁，共一百零五頁，編輯于2023年，星期一7

當dij=dji

(i,j∈V)時，問題被稱為對稱型TSP，否則稱為非對稱型TSP。若對所有1≤i,j,k≤n

，有不等式dij+djk≥dik成立，則問題被稱為是滿足三角形不等式的，簡稱為ΔTSP。第七頁，共一百零五頁，編輯于2023年，星期一82.擴展TSP(1)瓶頸TSP

瓶頸問題是最早從TSP延伸出來的一種擴展型TSP，其含義與經(jīng)典的TSP類似，僅目標不同，要求巡回路線中經(jīng)過的最長距離最短，即最小化瓶頸距離。該情形體現(xiàn)了那些并不追求總巡回路線最短，而只希望在巡回路線中每次從一個地點至另一個地點的單次行程盡可能短的實際應用問題的特征。第八頁，共一百零五頁，編輯于2023年，星期一9

從嚴格的數(shù)學意義而言，瓶頸TSP（簡稱BTSP）并沒有降低問題的難度，也未能提供任何特殊的解決辦法。瓶頸TSP的數(shù)學模型與標準TSP類似，僅目標函數(shù)不同：

由于目標函數(shù)為瓶頸值，故求得的最佳巡回路線與標準TSP的往往截然不同。第九頁，共一百零五頁，編輯于2023年，星期一10(2)最小比率TSP最小比率TSP（簡稱MRTSP）是從經(jīng)典TSP引申出來的另一個變形問題，假定從一個城市走到另一個城市可得到某種收益（記為），則MRTSP的目標就是確定最佳行走路線，使得回路的總行程與總收益之比最小。這種優(yōu)化目標的思想類似于人們?nèi)粘Ｉ钪薪?jīng)常使用的費用效益比，與單純的總行程最短相比，往往更具實際意義。第十頁，共一百零五頁，編輯于2023年，星期一11

假定收益的數(shù)學性質(zhì)與相同，則最小比率TSP的數(shù)學模型也與標準TSP類似，僅目標函數(shù)不同：

毫無疑問，由于目標函數(shù)中的非線性因素，最小比率TSP的求解比之標準TSP顯得更為困難。第十一頁，共一百零五頁，編輯于2023年，星期一12(3)多人TSP

若標準TSP中，出發(fā)點有多個推銷員同時出發(fā)，各自行走不同的路線，使得所有的城市都至少被訪問過一次，然后返回出發(fā)點，要求所有推銷員的總行程最短，則問題就成為一個多人的旅行商問題（簡記MTSP）。令決策變量則MTSP的數(shù)學模型為：第十二頁，共一百零五頁，編輯于2023年，星期一13

假定原問題為對稱型MTSP，V={v0,v1,…vn-1}，v0為名推銷員出發(fā)點，記V‘={v01,v02,…v0m;v0,v1,…vn-1}，擴大的m-1個頂點稱為“人造頂點”，其距離矩陣也相應擴大，其中，位于出發(fā)點的m個頂點相互間的距離設定為∞，其他數(shù)值不變。第十三頁，共一百零五頁，編輯于2023年，星期一14二、多面體理論從上世紀70年代開始的關于算法復雜性的研究表明，要想為TSP找到一個好的算法，也即多項式算法，似乎是不可能的。由于推銷員的每條路線可以用一個以1開始的排列來表示，因此所有可能的路線有條。這樣，若用枚舉法來解決這一問題，即使不太大，例如n＝30，用目前最快的計算機，也要化幾百萬年才能求出一條最短的路線。第十四頁，共一百零五頁，編輯于2023年，星期一15

早在1954年，Dantzig等人就曾提出過一種方法（非多項式算法），并且求出了一個42城市的TSP最優(yōu)解。到了1960年代，不少人用分支定界法解決了許多有幾十個城市的TSP。還有人提出了一些近似方法，也解決了許多有幾十個城市甚至上百個城市的TSP（有時找到的僅是近似解）。更值得注意的是，從1970年代中期開始，Grotschel與Padberg等人深入研究了TS多面體的最大面（facet），并從所得結果出發(fā)獲得了一種解TSP的新算法，可以解決一些有100多個城市的TSP，且都在不長的時間內(nèi)找到了最優(yōu)解。第十五頁，共一百零五頁，編輯于2023年，星期一16

考慮個頂點的完全圖Kn

，則解TSP就相當于在中求一條總長度最短的Hamilton回路?，F(xiàn)在，對每條邊ej，定義一個變量xj與之對應，這樣，TSP的一條路線T，即Kn的一條Hamilton回路，就可對應一個向量X={x1,x2,….xm}，其中，第十六頁，共一百零五頁，編輯于2023年，星期一17

稱X為路線T的關聯(lián)向量，其m=n(n-2)/2個分量中，恰好有個為1，其余的都為0。圖有許多Hamilton回路，設為T1,T2…Ts,，對應的關聯(lián)向量記為X1,X2…Xs

，在m維空間Rm中，考慮這些向量生成的凸包（convexhull）Qn

：第十七頁，共一百零五頁，編輯于2023年，星期一18

Qn是Rm中的一個凸多面體，稱做TS多面體。顯然，Qn是有界的，其極點正好是Kn的Hamilton回路關聯(lián)向量。研究Qn的面非常重要的，因為根據(jù)線性不等式及凸多面體的理論，Qn一定是某一個有限線性不等式組的解集合，或者說，Qn一定是有限多個半空間的交。因此，如果能找出定義Qn的線性不等式組來，就可將TSP作為一個線性規(guī)劃來解。第十八頁，共一百零五頁，編輯于2023年，星期一19TS多面體研究中的一個重要問題就是尋找能導出Qn最大面的不等式，Grotschel等人發(fā)現(xiàn)了一類很重要的能導出最大面的梳子不等式，并予以了證明。此外，還有其它能導出最大面的不等式，如團樹不等式等?？梢姡琎n的最大面極多，曾經(jīng)計算過由梳子不等式所導出的最大面?zhèn)€數(shù)如表7－1所示：n6810203050120c(n)604142088419701.5*10181.5*103110602*10179表7－1第十九頁，共一百零五頁，編輯于2023年，星期一20

可以看出，當增大時，最大面?zhèn)€數(shù)增長得非?？臁Ｔ赥S多面體理論的基礎上，可以考慮先解TSP的松弛問題，如果得到的最優(yōu)解正好是某一條路線的關聯(lián)向量，那么就找到TSP的最優(yōu)解了；否則，就設法找一些新的不等式作為額外約束，再解新的線性規(guī)劃，直至找到恰好是關聯(lián)向量的最優(yōu)解。這種做法的基本思想與解整數(shù)規(guī)劃的割平面法是同一類的，Gotschel等人曾用這種方法解過有120個城市的TSP，所增加的不等式只有子回路消去不等式與梳子不等式兩類，在進行了13輪計算后，即解了13個線性規(guī)劃后，就找到了TSP的精確最優(yōu)解，每一輪的當時計算時間僅在30秒至2分鐘之間。有趣的是，當n=120時，僅梳子不等式就有2*10179個，但在計算過程中，總共卻只（憑經(jīng)驗）添加了96個子回路消去不等式與梳子不等式。第二十頁，共一百零五頁，編輯于2023年，星期一21

當然，用該方法有時會找不到TSP的最優(yōu)解，因為很可能在進行了幾輪迭代后，卻找不到新的不等式。Padborg與Hong曾計算了74個TSP，其中54個得到了最優(yōu)解，其余的雖未得到最優(yōu)解，卻得到了很好的下界，如果與近似方法配合，可以估計近似解的精確程度。如，他們解過一個有313個城市的TSP，獲得一個下界41236.46，而用近似方法能得到一條長為41349的路線，于是可估計出所得近似解與最優(yōu)解的誤差不超過0.26%。第二十一頁，共一百零五頁，編輯于2023年，星期一22§7-2求解算法一、下界和上界算法1.下界（1）下界b1和b2

針對TSP對應圖的鄰接矩陣，將矩陣中每一行最小的元素相加，就可得到一個簡單的下界b1。經(jīng)進一步改進，可得到更好的下界：考慮一個TSP的完整解，在每條路徑上，每個城市都有兩條鄰接邊，一條進，一條出，那么，如果把矩陣中每一行最小的兩個元素相加再除以2（不失一般性，可假定圖中所有距離權重都為整數(shù)），再對其結果向上取整，就可得到一個合理的下界b2。顯然，b2≥b1，因此，一般不采用b1作為TSP的下界。第二十二頁，共一百零五頁，編輯于2023年，星期一23例1已知TSP及其距離矩陣如圖7－1所示，試求其下界271563134253984(a)無向圖圖7－1無向圖及距離矩陣(b)距離矩陣第二十三頁，共一百零五頁，編輯于2023年，星期一24解：將矩陣中每一行最小的元素相加，1+3+1+3+2=10，即得b1=10。將矩陣中每一行最小的兩個元素相加再除以2，再對結果向上取整，即可得b2=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14。第二十四頁，共一百零五頁，編輯于2023年，星期一25（2）下界b3為便于描述下界b3，先定義如下符號：T：對稱TSP問題；n：結點總個數(shù)；w(i,j)：結點i與j之間距離；dmin(i,k)：與第i個結點關聯(lián)的所有邊中第k(k=1,2,3)長邊的長度；dmin_j(i,k)：與第i個結點關聯(lián)的所有邊中第k(k=1,2,3)長邊的另一個結點的編號(其中一個結點編號為i)；node_base(i)=dmin_j(i,1)+dmin_j(i,2)：表示與i點關聯(lián)邊中長度最短的兩條邊之和；C*(T)：最優(yōu)回路長度；第二十五頁，共一百零五頁，編輯于2023年，星期一26

于是，dmin(i,1)代表與第i個結點關聯(lián)的所有邊中最長邊的長度，dmin_j(i,1)代表與第i個結點關聯(lián)的所有邊中次長邊的另一個結點編號(其中一個結點編號為i)，第i結點的dmin(i,k)和dmin_j(i,k)可由距離矩陣w輕易求得。通過對下界b2進行改進，可以得出一個求對稱型TSP更好的下界b3。在求b2的過程中，只有當與每一結點關聯(lián)的邊中長度最小的兩條邊都出現(xiàn)在最優(yōu)TSP回路中時，等號才成立，下面就來分析如何提高這個下界。第二十六頁，共一百零五頁，編輯于2023年，星期一27

對結點i而言，設e(i)1與e(i)2分別為與結點i關聯(lián)的邊中長度最小的兩條邊，其長度分別為dmin(i,1)和dmin(i,2)。在對稱型TSP回路中，由于有且僅有兩條邊與每一結點關聯(lián)，因此，并不是與每個結點關聯(lián)的最小兩條邊都能出現(xiàn)在最優(yōu)TSP回路中，這意味可以在node_base(i)的基礎上增加TSP回路的長度，將在這種情況下增加的長度記為Adjust(T)，現(xiàn)在分析如何計算Adjust(T)。第二十七頁，共一百零五頁，編輯于2023年，星期一28

對結點i的e(i)1，邊e(i)1的一個結點為i，另一個結點為j=dmin_j(i,1)，若e(i)1也是結點j關聯(lián)邊中最小的兩條邊之一，即i=dmin_j(j,1)或i=dmin_j(j,2)，則對邊e(i)1來說就不需要調(diào)整，否則按以下方式調(diào)整：第二十八頁，共一百零五頁，編輯于2023年，星期一29若e(i)1不是結點j=dmin_j(i,1)關聯(lián)邊中最小的兩條邊之一，則只有以下兩種情況：①選中e(i)1到TSP回路中此時對結點i不需調(diào)整，對結點j來說，由于邊e(i)1出現(xiàn)在最優(yōu)回路中，而e(i)1不是結點j關聯(lián)邊中最小的兩條邊之一，因此會造成結點j關聯(lián)邊中最小的兩條邊中至少有一條不會出現(xiàn)在最優(yōu)回路中，從而對結點j而言，在node_base(i)的基礎上至少會增加的長度為dmin(i,1)–dmin(j,2)。第二十九頁，共一百零五頁，編輯于2023年，星期一30②不選中e(i)1到TSP回路中此時對結點i需要調(diào)整，由于邊e(i)1不在回路中，故其在node_base(i)的基礎上至少會增加的長度為dmin(i,3)–dmin(i,1)。此時對結點j來說，由于與它關聯(lián)的最短兩條邊仍然可能在回路中，因此不須調(diào)整。第三十頁，共一百零五頁，編輯于2023年，星期一31

對于①和②，必須有且僅有一種情況出現(xiàn)，現(xiàn)取兩種情況中增加長度小的值，因而回路的長路一定會在b2的基礎上增加：add_node(i,1)=1/2*min(dmin(i,3)–dmin(i,1),dmin(i,1)–dmin(j,2))。對結點i的e(i)2，邊e(i)2的一個結點為i，另一個結點為j=dmin_j(i,2)，若e(i)2也是結點j關聯(lián)邊中最小的兩條邊之一，則對邊e(i)2來說不需要調(diào)整，否則按與前面類似的方法計算調(diào)整值。經(jīng)分析，其在base(T)的基礎上至少要增加：add_node(i,2)=1/2*min(dmin(i,3)–dmin(i,2),dmin(i,2)–dmin(j,2))。第三十一頁，共一百零五頁，編輯于2023年，星期一32

將每個結點都按上述方法進行一次調(diào)整，其調(diào)整累加和就是Adjust(T)，可寫成如下公式：第三十二頁，共一百零五頁，編輯于2023年，星期一33

將問題T中所有結點的基本長度node_base(T)累加之和的一半稱為T的基本長度，并用base(T)來表示，可寫成如下公式：第三十三頁，共一百零五頁，編輯于2023年，星期一34

于是，有C*(T)≥base(T)+Adjust(T)=b3，即b3=b2+Adjust(T)。由以上分析，不難得出求對稱TSP下界b3的算法：第三十四頁，共一百零五頁，編輯于2023年，星期一35Step1.計算base(T)：

get_base()

{

i:LongFori=1Tonbase=base+dmin(i,1)+dmin(i,2)}第三十五頁，共一百零五頁，編輯于2023年，星期一36Step2.計算Adjust(T)：get_adjust(){i,ii1,ii2:LongFori=1Ton{ii1=dmin_j(i,1);ii2=dmin_j(i,2)Ifi<>dmin_j(ii1,1)Andi<>dmin_j(ii1,2)adjust=adjust+min(dmin(i,3)-dmin(i,1),dmin(i,1)-dmin(ii1,2))Ifi<>dmin_j(ii2,1)Andi<>dmin_j(ii2,2)adjust=adjust+min(dmin(i,3)-dmin(i,2),dmin(i,2)-dmin(ii2,2))}}第三十六頁，共一百零五頁，編輯于2023年，星期一37對例1而言，可計算其b3如下：dmin(1,1)=1；dmin_j(1,1)=3；dmin(1,2)=3；dmin_j(1,2)=2；dmin(1,3)=5；dmin_j(1,3)=4；dmin(2,1)=3；dmin_j(2,1)=1；dmin(2,2)=6；dmin_j(2,2)=3；dmin(2,3)=7；dmin_j(2,3)=4；dmin(3,1)=1；dmin_j(3,1)=1；dmin(3,2)=2；dmin_j(3,2)=5；dmin(3,3)=4；dmin_j(3,3)=4；271563134253984(a)無向圖圖7－1無向圖第三十七頁，共一百零五頁，編輯于2023年，星期一38dmin(4,1)=3；dmin_j(4,1)=5；dmin(4,2)=4；dmin_j(4,2)=3；dmin(4,3)=5；dmin_j(4,3)=1；dmin(5,1)=2；dmin_j(5,1)=3；dmin(5,2)=3；dmin_j(5,2)=4；dmin(5,3)=8；dmin_j(5,3)=1；271563134253984(a)無向圖圖7－1無向圖第三十八頁，共一百零五頁，編輯于2023年，星期一39add_node(1,1)=0;add_node(1,2)=0;add_node(2,1)=0;add_node(2,2)=1/2×min((7-6),(6-2))=1/2;add_node(3,1)=0;add_node(3,2)=1/2×min((5-4),(4-2))=1/2;

add_node(4,1)=0;add_node(4,2)=0

;add_node(5,1)=0;add_node(5,2)=

0;

所以，Adjust(T)=1/2+1/2=1，得b3=b2+Adjust(T)=14+1=15。第三十九頁，共一百零五頁，編輯于2023年，星期一402.上界事實上，TSP的任何可行解都是上界，這里，給出求TSP上界U1的貪心方法思想。算法步驟如下：第四十頁，共一百零五頁，編輯于2023年，星期一41Step1.圖G={V,E}中頂點個數(shù)為n=|V|，邊的條數(shù)m=|E|，令i為出發(fā)點，TSP_edge_n為加入到TSP回路中邊的條數(shù)且TSP_edge_n=0，TSP_edge為已加入到TSP回路中的邊集合且TSP_edge={}，k為當前頂點且k=i。Step2.從邊集

中選中一條代價最小的一條邊(k,h)，并執(zhí)行

TSP_edge_n=TSP_edge_n+1；

TSP_edge=TSP_edge+{(k,h)}；

k=h。Step3.若TSP_edge_n<(n-1)，則轉Step2。Step4.將邊(k,i)加入到TSP_edge中。第四十一頁，共一百零五頁，編輯于2023年，星期一42

求解結束后，TSP_edge中的邊都在TSP回路中。對例1，可用上述算法求得其路徑為：1→3→5→4→2→1，路徑長度1+2+3+7+3=16，這是TSP的一個上界U1。綜合上下界，就可得到例1目標函數(shù)的界為[15,16]。271563134253984(a)無向圖圖7－1無向圖第四十二頁，共一百零五頁，編輯于2023年，星期一43二、分支定界法二、分支定界法分支定界法是一種在表示問題解空間的樹上進行系統(tǒng)搜索的精確算法，這里，介紹兩種求解TSP的分支定界方法。第四十三頁，共一百零五頁，編輯于2023年，星期一44.基于上下界的分支定界法為用分支定界法求解TSP，需要計算某些邊在TSP回路中和某些邊不在TSP回路中等情況下的下界。若采用下界b2計算，由于每個頂點最多只有兩個關聯(lián)邊在TSP回路中，已在TSP回路中的邊則限制該邊的其它鄰接邊加入，因此，針對每個頂點，分4種情況來計算：第四十四頁，共一百零五頁，編輯于2023年，星期一45(1)若某頂點沒有關聯(lián)邊在TSP回路中，則該頂點的計算方法與計算b2的方法相同，即把該頂點關聯(lián)的最短兩邊長度之和的一半加入到下界中；(2)若某頂點關聯(lián)的邊已有兩條邊e1和e2在TSP回路中，則不需要再加入與該頂點關聯(lián)最小兩條邊的長度，即此時把e1和e2長度之和的一半加入到下界中；(3)若某頂點關聯(lián)的邊已有一條邊e1在TSP回路中，則只需要再加入與該頂點關聯(lián)的最小邊長度，即把e1和該頂點關聯(lián)的最短一條邊的長度之和的一半加入到下界中；(4)若某頂點關聯(lián)邊集的子集E1不能出現(xiàn)在TSP回路中，則將E1從圖中刪除再計算b2即可；如某頂點已有兩關聯(lián)邊在回路中，則可將其它關聯(lián)邊刪除，同樣，可以將會與已加入到回路中的邊形成子圈的邊刪除。第四十五頁，共一百零五頁，編輯于2023年，星期一46

如例1中所示的無向圖，若其TSP回路包含邊(1,4)，則該部分解的下界b2=((1+5)+(3+6)+(1+2)+(3+5)+(2+3))/2=16，此時計算其下界時，由于邊(1,4)已在回路中，故與頂點1關聯(lián)的邊只需再加入一條最短邊(1,3)。若TSP回路包含邊(1,2)和(2,4)，則這時的下界b2=((1+3)+(3+7)+(1+2)+(3+7)+(2+3))/2=16。271563134253984(a)無向圖圖7－1無向圖第四十六頁，共一百零五頁，編輯于2023年，星期一47

為描述方便，用eij

=1表示邊(i,j)在TSP回路中，eij

=0表示邊(i,j)不在TSP回路中。下面給出用分支定界法求解例1的過程（如圖7－2所示）：第四十七頁，共一百零五頁，編輯于2023年，星期一48圖7－2分支定界求解過程U1=16e13=0e13=1b2=17.5>U1,故剪支e12=0e12=1b2=17>U1,故剪支得最優(yōu)解e12=e13=e24=e35=e54=1,

e14=e15=e23=e25=e34=0e25=0e25=1b2=18.5>U1=16,故剪支此時有e14=e15=e23=0此時有e24=e35=e54=1,e34=0第四十八頁，共一百零五頁，編輯于2023年，星期一49(1)用貪心算法求得上界U1=16；

(2)假定邊(1,3)不在TSP回路中，即e13=0，此時，b2=((5+3)+(3+6)+(4+2)+(3+4)+(2+3))/2=17.5，由于b2=17.5>U1=16，因此邊(1,3)一定在回路中，即e13=1；(3)在e13=1的情況下，假定e12=0，此時b2=((1+5)+(6+7)+(1+2)+(3+4)+(2+3))/2=17，由于b2=17>U1=16，因此邊(1,2)一定在回路中，即e12=1；第四十九頁，共一百零五頁，編輯于2023年，星期一50(4)在e12=e13=1的情況下，由于頂點1已有兩條關聯(lián)邊在最優(yōu)回路中，因此在圖7－1中刪去邊(1,4)和(1,5)，由于邊(2,3)與邊(1,2)、(1,3)形成圈，因此在圖7－1中刪去邊(2,3)，即此時e14=e15=e23=0；(5)在e12=e13=1，e14=e15=e23=0的情況下，假定e25=1，此時b2=((1+3)+(3+9)+(1+2)+(3+4)+(2+9))/2=18.5，由于b2=18.5>U1=16，因此邊(2,5)一定不在回路中，即e25=0；第五十頁，共一百零五頁，編輯于2023年，星期一51在e12=e13=1，e14=e15=e23=e25=0的情況下，由于與頂點2關聯(lián)的邊有且只有2條在回路中，因此有e24=1，進而有e35=e54=1，e34=0。

至此，得到最優(yōu)解：e12=e13=e24=e35=e54=1，e14=e15=e23=e25=e34=0；最優(yōu)目標值：1+2+3+7+3=16。第五十一頁，共一百零五頁，編輯于2023年，星期一522.基于降階的分支定界法對于有向TSP的距離距陣，可通過不同情況下上下界的對比來確定某些邊(i,j)一定在或不在回路中。如果能確定(i,j)一定在回路中，由于每個頂點分別有且只有一條入邊和出邊，從而可確定頂點i的其它出邊一定不在回路中，也可以確定頂點j的其它出邊一定不在回路中，因此可將這些邊從距離距陣中去掉，從而達到降低矩陣階數(shù)的目的。這里，以一個具體的例子來予以說明。第五十二頁，共一百零五頁，編輯于2023年，星期一53例2已知有向TSP的距離矩陣如下：第五十三頁，共一百零五頁，編輯于2023年，星期一54解:

由于每個頂點都必須有一條入邊和出邊，因此將頂點i的所有出邊的權值減去所有出邊權值的最小值min_out(i)，不會影響最優(yōu)解，僅最優(yōu)值在原來的基礎上減少了min_out(i)。于是，可以將距離矩陣的每一行和每一列都減去該行或該列的最小值，直至每行每列都含有0為止。將上述矩陣的每行分別減去該行的最小值3,4,16,7,25,3，就得到如下縮減之后的矩陣：第五十四頁，共一百零五頁，編輯于2023年，星期一55

該縮減矩陣所對應TSP的最優(yōu)解與原來的相同，但最優(yōu)值比原來減少了3+4+16+7+25+3=58。由于矩陣中第3、4列中不含0元素，因此可繼續(xù)縮減成：第五十五頁，共一百零五頁，編輯于2023年，星期一56該縮減矩陣所對應TSP的最優(yōu)解與原來的相同，但最優(yōu)值比原來減少了3+4+16+7+25+3=58。由于矩陣中第3、4列中不含0元素，因此可繼續(xù)縮減成：第五十六頁，共一百零五頁，編輯于2023年，星期一57

其最優(yōu)值比原來減少58+15+8=81，這個81可作為該TSP初始的下界值b。第五十七頁，共一百零五頁，編輯于2023年，星期一58按e63=1和e63=0將解分成兩種情況：(1)e63=0

此時，邊(6,3)不能出現(xiàn)在回路中，其權值在這種情況下為∞，因此，距離矩陣可修改為：第五十八頁，共一百零五頁，編輯于2023年，星期一59

由于第3列沒有0元素，故用第3列各元素減去其最小元素48，得如下縮減矩陣：

此時的下界b=81+48=129。第五十九頁，共一百零五頁，編輯于2023年，星期一60(2)e63=1

此時，邊(6,3)已出現(xiàn)在回路中，從頂點6出發(fā)的其它邊都不可能在回路中，因此可刪去第6行；同理，進入到頂點3的其它邊都不可能在回路中，因此又可刪去第3列。此時，邊(3,6)不可能出現(xiàn)在回路中，令邊(3,6)的權值為∞，矩陣化為：第六十頁，共一百零五頁，編輯于2023年，星期一61繼續(xù)依次計算，并實施分支和定界，具體過程如圖7－3所示：圖7－3降階分支定界過程b=81e63=0e63=1b=129e46=0e46=1b=113e21=0e21=1b=81b=81b=84b=101e14=1e14=0b=84b=112得可行回路(1,4,6,3,5,2,1),回路總長104，由此可將下界b大于104的分支剪去。第六十一頁，共一百零五頁，編輯于2023年，星期一62e63=1，e46=0下的縮減矩陣：第六十二頁，共一百零五頁，編輯于2023年，星期一63e63=e46=1下的縮減矩陣：第六十三頁，共一百零五頁，編輯于2023年，星期一64e63=e46=1，e21=0下的縮減矩陣：第六十四頁，共一百零五頁，編輯于2023年，星期一65e63=e46=e21=1下的縮減矩陣：第六十五頁，共一百零五頁，編輯于2023年，星期一66e63=e46=e21=1，e14=0下的縮減矩陣：第六十六頁，共一百零五頁，編輯于2023年，星期一67e63=e46=e21=e14=1下的縮減矩陣：第六十七頁，共一百零五頁，編輯于2023年，星期一68e63=e46=1，e21=e51=0下的縮減矩陣：第六十八頁，共一百零五頁，編輯于2023年，星期一69e63=e46=e51=1，e21=0下的縮減矩陣：第六十九頁，共一百零五頁，編輯于2023年，星期一70e63=e46=e51=1，e21=e14=0下的縮減矩陣：第七十頁，共一百零五頁，編輯于2023年，星期一71e63=e46=e51=e14=1，e21=0下的縮減矩陣：第七十一頁，共一百零五頁，編輯于2023年，星期一72

最后可得到兩個最優(yōu)TSP回路：(1,4,6,3,2,5,1)和(1,4,6,3,5,2,1)，最優(yōu)回路長度為104。若將無向圖中的每條邊看成有向圖中方向相反的兩條邊，則無向圖也可看成是有向圖，因此，基于降階的分支定界法也可用來求解無向TSP問題。第七十二頁，共一百零五頁，編輯于2023年，星期一73三、動態(tài)規(guī)劃法定理1TSP滿足最優(yōu)性原理。

最優(yōu)化原理可以表述為：“一個過程的最優(yōu)策略具有這樣的性質(zhì),即無論初始狀態(tài)和初始決策如何,對于先前決策所形成的狀態(tài)而言,其以后的所有決策必構成最優(yōu)策略，”第七十三頁，共一百零五頁，編輯于2023年，星期一74證：設s,s1,s2,…,sp,s是從s出發(fā)的一條總長最短的簡單回路，假設從s到下一個城市s1已經(jīng)求出，則問題轉化為求從s1到s的最短路徑，顯然s1,s2,…,sp,s一定構成一條從s1到s的最短路徑。若不然，設s1,r1,r2,…,rq,s是一條從s1到s的最短路徑且經(jīng)過n-1個不同城市，則s,s1,r1,r2,…,rq,s將是一條從s出發(fā)的路徑長度最短的簡單回路且比s,s1,s2,…,sp,s要短，從而導致矛盾。所以，TSP滿足最優(yōu)性原理。第七十四頁，共一百零五頁，編輯于2023年，星期一75

設TSP頂點編號分別為0，1，2，…，n，假設從頂點0出發(fā)，令d(i,V')表示從頂點i出發(fā)經(jīng)過V'中各頂點一次且僅一次，最后回到出發(fā)點0的最短路徑長度，中間計算過程中的d(k,V'－{k})也表示從頂點k

出發(fā)經(jīng)過V'－{k}

中各頂點一次且僅一次，最后回到出發(fā)點0（注意不是k）的最短路徑長度。開始時，V'=V－{i}，cij為頂點i至頂點j的距離，于是，TSP的動態(tài)規(guī)劃遞推函數(shù)可寫成：第七十五頁，共一百零五頁，編輯于2023年，星期一76d(i,V')=min{cik

+d(k,V'－{k})}(k∈V')d(k,{})=ck0

(k≠0

)例3求解有向TSP：第七十六頁，共一百零五頁，編輯于2023年，星期一77解：從城市0出發(fā)經(jīng)城市1、2、3然后回到城市0的最短路徑長度為：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}這是最后一個階段的決策，而d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}，d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}，d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}；這一階段的決策又依賴于下述計算結果：第七十七頁，共一百零五頁，編輯于2023年，星期一78d(1,{2})=c12+d(2,{})，d(2,{3})=c23+d(3,{})，d(3,{2})=c32+d(2,{})，d(1,{3})=c13+d(3,{})，d(2,{1})=c21+d(1,{})，d(3,{1})=c31+d(1,{})；而下式可以直接獲得（括號中是該決策引起的狀態(tài)轉移）：d(1,{})=c10=5(1→0)，d(2,{})=c20=6(2→0)，d(3,{})=c30=3(3→0)；第七十八頁，共一百零五頁，編輯于2023年，星期一79再向前倒推，有：d(1,{2})=c12+d(2,{})=2+6=8(1→2)，d(1,{3})=c13+d(3,{})=3+3=6(1→3)，d(2,{3})=c23+d(3,{})=2+3=5(2→3)，d(2,{1})=c21+d(1,{})=4+5=9(2→1)，d(3,{1})=c31+d(1,{})=7+5=12(3→1)，d(3,{2})=c32+d(2,{})=5+6=11(3→2)；第七十九頁，共一百零五頁，編輯于2023年，星期一80再向前倒推，有：d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}=min{2+5,3+11}=7(1→2)，d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}=min{4+6,2+12}=10(2→1)，d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}=min{7+8,5+9}=14(3→2)；第八十頁，共一百零五頁，編輯于2023年，星期一81最后有：

d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}=min{3+7,6+10,7+14}=10(0→1)。即，從頂點0出發(fā)的TSP最短回路長度為10，回路路徑為：0→1→2→3→0。第八十一頁，共一百零五頁，編輯于2023年，星期一82四、近似算法

由于精確式算法所能求解的問題規(guī)模非常有限，實際中真正使用的往往都是多項式階數(shù)的近似算法或啟發(fā)式算法，算法的好壞用C/C*≤ε來衡量，其中，C為近似算法所得的總行程，C*為最優(yōu)總行程，ε為最“壞“情況下近似與最優(yōu)總行程之比所不超過的上界值。這里，列舉幾個常見的TSP快速近似算法。第八十二頁，共一百零五頁，編輯于2023年，星期一83

旅行售貨員問題的一些特殊性質(zhì)：比如，費用函數(shù)w往往具有三角不等式性質(zhì)，即對任意的3個頂點u,v,w∈V，有：w(u,w)≤w(u,v)+w(v,w)。當圖G中的頂點就是平面上的點，任意2頂點間的費用就是這2點間的歐氏距離時，費用函數(shù)w就具有三角不等式性質(zhì)。

對于給定的無向圖G，可以利用找圖G的最小生成樹的算法設計找近似最優(yōu)的旅行售貨員回路的算法。

第八十三頁，共一百零五頁，編輯于2023年，星期一84

當費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。

voidapproxTSP(Graphg){(1)選擇g的任一頂點r；

(2)用Prim算法找出帶權圖g的一棵以r為根的最小生成樹T；

(3)前序遍歷樹T得到的頂點表L；

(4)將r加到表L的末尾，按表L中頂點次序組成回路H，作為計算結果返回；}第八十四頁，共一百零五頁，編輯于2023年，星期一85(b)表示找到的最小生成樹T；(c)表示對T作前序遍歷的次序；(d)表示L產(chǎn)生的哈密頓回路H；(e)是G的一個最小費用旅行售貨員回路。

為什么：當費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。第八十五頁，共一百零五頁，編輯于2023年，星期一86答：存在一個最優(yōu)TSP回路TSPOPT，TSPOPT中共有n條邊，現(xiàn)去掉TOPT中最長的一條邊，得路徑POPT，POPT中共有n-1條邊，其總權值之和WTSP大于等于最小生成樹的總權值之和WT；即WTSP≥WT,下面只需證明該算法求得的TSP回路總長度之和WA小于等于2WT即可；把最小生成樹中的邊重復一次，再根據(jù)三角不等式就可得出結論（多次利用三角不等式）。

為什么：當費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。第八十六頁，共一百零五頁，編輯于2023年，星期一87

把最小生成樹中的邊重復一次，再根據(jù)三角不等式就可得出結論（多次利用三角不等式）。（d）中藍色的邊為原來不在最小生成樹中的邊，最小生成樹中的邊重復一次及不在(d)中，但在(b)中的邊反復利用三角不等式就可得出結論。第八十七頁，共一百零五頁，編輯于2023年，星期一881.插入算法插入型算法可按插入規(guī)則的不同而分為若干類，其一般思想為：Step1.通過某種插入方式選擇插入邊(i,j)和插入點k，將k

插入i

和j之間,形成{…,i,k,j,…}。Step2.依次進行，直至形成回路解。適用范圍：對稱型△TSP。具體實施中，可將出發(fā)點取遍V中各點而得到多個解，并從中選擇最好的一個，但此時的時間復雜度增加了n倍。主要的插入型算法有：第八十八頁，共一百零五頁，編輯于2023年，星期一89(1)最近插入法最壞情況：ε=2；時間復雜度：O(n2)。(2)最小插入法最壞情況：ε=2；時間復雜度：O(n2lgn)。(3)任意插入法最壞情況：ε=21gn+0.16；時間復雜度：O(n2)。(4)最遠插入法最壞情況：ε=21gn+0.16；時間復雜度：O(n2)。(5)凸核插入法最壞情況：ε=未知；時間復雜度：O(n2lgn)。第八十九頁，共一百零五頁，編輯于2023年，星期一90插入法(InsertionMethod)

1任選一節(jié)點為起點a；2尋找距離節(jié)點a最近的節(jié)點b作為下一個造訪的節(jié)點，形成a-b-a的子回路；3尋找距離子回路最近的節(jié)點k作為下一個插入點；4尋找插入成本最小的位置(i-j)，將k插入i-j之間，形成新的子回路；

?插入成本：Cik+Ckj-Cij5重復步驟3~4，直到所有節(jié)點均已插入回路之中，即形成一個TSP的可行解。第九十頁，共一百零五頁，編輯于2023年，星期一91插入法743875534833733774557744888445584541任選一節(jié)點為起點a；2尋找距離節(jié)點a最近的節(jié)點b作為下一個造訪的節(jié)點，形成a-b-a的子回路；3尋找距離子回路最近的節(jié)點k作為下一個插入點；4尋找插入成本最小的位置(i-j)，將k插入i-j之間，形成新的子回路；

?插入成本：Cik+Ckj-Cij5重復步驟3~4，直到所有節(jié)點均已插入回路之中，即形成一個TSP的可行解。第九十一頁，共一百零五頁，編輯于2023年，星期一922.最近鄰算法Ste