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

關(guān)于數(shù)學(xué)建模經(jīng)典問題——旅行商問題第1頁，共105頁，2023年，2月20日，星期四2第7章旅行商問題1.問題概述

2.求解算法

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

目錄2.5.競賽題2.3.動態(tài)規(guī)劃法2.5.近似算法第2頁，共105頁，2023年，2月20日，星期四3§7-1問題概述

一、數(shù)學(xué)模型

1.標(biāo)準(zhǔn)TSP

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

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

記為賦權(quán)圖G=(V,E)，V為頂點集，E為邊集，各頂點間的距離dij已知。設(shè)則經(jīng)典的TSP可寫為如下的數(shù)學(xué)規(guī)劃模型：第5頁，共105頁，2023年，2月20日，星期四6

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

當(dāng)dij=dji

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

，有不等式dij+djk≥dik成立，則問題被稱為是滿足三角形不等式的，簡稱為ΔTSP。第7頁，共105頁，2023年，2月20日，星期四82.擴(kuò)展TSP(1)瓶頸TSP

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

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

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

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

毫無疑問，由于目標(biāo)函數(shù)中的非線性因素，最小比率TSP的求解比之標(biāo)準(zhǔn)TSP顯得更為困難。第11頁，共105頁，2023年，2月20日，星期四12(3)多人TSP

若標(biāo)準(zhǔn)TSP中，出發(fā)點有多個推銷員同時出發(fā)，各自行走不同的路線，使得所有的城市都至少被訪問過一次，然后返回出發(fā)點，要求所有推銷員的總行程最短，則問題就成為一個多人的旅行商問題（簡記MTSP）。令決策變量則MTSP的數(shù)學(xué)模型為：第12頁，共105頁，2023年，2月20日，星期四13

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

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

考慮個頂點的完全圖Kn

，則解TSP就相當(dāng)于在中求一條總長度最短的Hamilton回路?，F(xiàn)在，對每條邊ej，定義一個變量xj與之對應(yīng)，這樣，TSP的一條路線T，即Kn的一條Hamilton回路，就可對應(yīng)一個向量X={x1,x2,….xm}，其中，第16頁，共105頁，2023年，2月20日，星期四17

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

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

：第17頁，共105頁，2023年，2月20日，星期四18

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

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

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

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

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

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

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

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

將每個結(jié)點都按上述方法進(jìn)行一次調(diào)整，其調(diào)整累加和就是Adjust(T)，可寫成如下公式：第32頁，共105頁，2023年，2月20日，星期四33

將問題T中所有結(jié)點的基本長度node_base(T)累加之和的一半稱為T的基本長度，并用base(T)來表示，可寫成如下公式：第33頁，共105頁，2023年，2月20日，星期四34

于是，有C*(T)≥base(T)+Adjust(T)=b3，即b3=b2+Adjust(T)。由以上分析，不難得出求對稱TSP下界b3的算法：第34頁，共105頁，2023年，2月20日，星期四35Step1.計算base(T)：

get_base()

{

i:LongFori=1Tonbase=base+dmin(i,1)+dmin(i,2)}第35頁，共105頁，2023年，2月20日，星期四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))}}第36頁，共105頁，2023年，2月20日，星期四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無向圖第37頁，共105頁，2023年，2月20日，星期四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無向圖第38頁，共105頁，2023年，2月20日，星期四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。第39頁，共105頁，2023年，2月20日，星期四402.上界事實上，TSP的任何可行解都是上界，這里，給出求TSP上界U1的貪心方法思想。算法步驟如下：第40頁，共105頁，2023年，2月20日，星期四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為當(dāng)前頂點且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)，則轉(zhuǎn)Step2。Step4.將邊(k,i)加入到TSP_edge中。第41頁，共105頁，2023年，2月20日，星期四42

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

如例1中所示的無向圖，若其TSP回路包含邊(1,4)，則該部分解的下界b2=((1+5)+(3+6)+(1+2)+(3+5)+(2+3))/2=16，此時計算其下界時，由于邊(1,4)已在回路中，故與頂點1關(guān)聯(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無向圖第46頁，共105頁，2023年，2月20日，星期四47

為描述方便，用eij

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

=0表示邊(i,j)不在TSP回路中。下面給出用分支定界法求解例1的過程（如圖7－2所示）：第47頁，共105頁，2023年，2月20日，星期四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第48頁，共105頁，2023年，2月20日，星期四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；第49頁，共105頁，2023年，2月20日，星期四50(4)在e12=e13=1的情況下，由于頂點1已有兩條關(guān)聯(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；第50頁，共105頁，2023年，2月20日，星期四51在e12=e13=1，e14=e15=e23=e25=0的情況下，由于與頂點2關(guān)聯(lián)的邊有且只有2條在回路中，因此有e24=1，進(jìn)而有e35=e54=1，e34=0。

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

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

該縮減矩陣所對應(yīng)TSP的最優(yōu)解與原來的相同，但最優(yōu)值比原來減少了3+4+16+7+25+3=58。由于矩陣中第3、4列中不含0元素，因此可繼續(xù)縮減成：第55頁，共105頁，2023年，2月20日，星期四56該縮減矩陣所對應(yīng)TSP的最優(yōu)解與原來的相同，但最優(yōu)值比原來減少了3+4+16+7+25+3=58。由于矩陣中第3、4列中不含0元素，因此可繼續(xù)縮減成：第56頁，共105頁，2023年，2月20日，星期四57

其最優(yōu)值比原來減少58+15+8=81，這個81可作為該TSP初始的下界值b。第57頁，共105頁，2023年，2月20日，星期四58按e63=1和e63=0將解分成兩種情況：(1)e63=0

此時，邊(6,3)不能出現(xiàn)在回路中，其權(quán)值在這種情況下為∞，因此，距離矩陣可修改為：第58頁，共105頁，2023年，2月20日，星期四59

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

此時的下界b=81+48=129。第59頁，共105頁，2023年，2月20日，星期四60(2)e63=1

此時，邊(6,3)已出現(xiàn)在回路中，從頂點6出發(fā)的其它邊都不可能在回路中，因此可刪去第6行；同理，進(jìn)入到頂點3的其它邊都不可能在回路中，因此又可刪去第3列。此時，邊(3,6)不可能出現(xiàn)在回路中，令邊(3,6)的權(quán)值為∞，矩陣化為：第60頁，共105頁，2023年，2月20日，星期四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的分支剪去。第61頁，共105頁，2023年，2月20日，星期四62e63=1，e46=0下的縮減矩陣：第62頁，共105頁，2023年，2月20日，星期四63e63=e46=1下的縮減矩陣：第63頁，共105頁，2023年，2月20日，星期四64e63=e46=1，e21=0下的縮減矩陣：第64頁，共105頁，2023年，2月20日，星期四65e63=e46=e21=1下的縮減矩陣：第65頁，共105頁，2023年，2月20日，星期四66e63=e46=e21=1，e14=0下的縮減矩陣：第66頁，共105頁，2023年，2月20日，星期四67e63=e46=e21=e14=1下的縮減矩陣：第67頁，共105頁，2023年，2月20日，星期四68e63=e46=1，e21=e51=0下的縮減矩陣：第68頁，共105頁，2023年，2月20日，星期四69e63=e46=e51=1，e21=0下的縮減矩陣：第69頁，共105頁，2023年，2月20日，星期四70e63=e46=e51=1，e21=e14=0下的縮減矩陣：第70頁，共105頁，2023年，2月20日，星期四71e63=e46=e51=e14=1，e21=0下的縮減矩陣：第71頁，共105頁，2023年，2月20日，星期四72

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

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

設(shè)TSP頂點編號分別為0，1，2，…，n，假設(shè)從頂點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ù)可寫成：第75頁，共105頁，2023年，2月20日，星期四76d(i,V')=min{cik

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

(k≠0

)例3求解有向TSP：第76頁，共105頁，2023年，2月20日，星期四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})}；這一階段的決策又依賴于下述計算結(jié)果：第77頁，共105頁，2023年，2月20日，星期四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)轉(zhuǎn)移）：d(1,{})=c10=5(1→0)，d(2,{})=c20=6(2→0)，d(3,{})=c30=3(3→0)；第78頁，共105頁，2023年，2月20日，星期四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)；第79頁，共105頁，2023年，2月20日，星期四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)；第80頁，共105頁，2023年，2月20日，星期四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。第81頁，共105頁，2023年，2月20日，星期四82四、近似算法

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

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

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

第83頁，共105頁，2023年，2月20日，星期四84

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

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

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

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

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

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

為什么：當(dāng)費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。第86頁，共105頁，2023年，2月20日，星期四87

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

插入i

和j之間,形成{…,i,k,j,…}。Step2.依次進(jìn)行，直至形成回路解。適用范圍：對稱型△TSP。具體實施中，可將出發(fā)點取遍V中各點而得到多個解，并從中選擇最好的一個，但此時的時間復(fù)雜度增加了n倍。主要的插入型算法有：第88頁，共105頁，2023年，2月20日，星期四89(1)最近插入法最壞情況：ε=2；時間復(fù)雜度：O(n2)。(2)最小插入法最壞情況：ε=2；時間復(fù)雜度：O(n2lgn)。(3)任意插入法最壞情況：ε=21gn+0.16；時間復(fù)雜度：O(n2)。(4)最遠(yuǎn)插入法最壞情況：ε=21gn+0.16；時間復(fù)雜度：O(n2)。(5)凸核插入法最壞情況：ε=未知；時間復(fù)雜度：O(n2lgn)。第89頁，共105頁，2023年，2月20日，星期四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重復(fù)步驟3~4，直到所有節(jié)點均已插入回路之中，即形成一個TSP的可行解。第90頁，共105頁，2023年，2月20日，星期四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重復(fù)步驟3~4，直到所有節(jié)點均已插入回路之中，即形成一個TSP的可行解。第91頁，共105頁，2023年，2月20日，星期四922.最近鄰算法Step