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

1、2021/3/271第第7章章 旅行商問題旅行商問題2021/3/272第第7章章 旅行商問題旅行商問題1.問題概述問題概述 2.求解算法求解算法 2.1.下界和上界算法下界和上界算法2.2.分支定界法分支定界法 目錄目錄2.5.競賽題競賽題2.3.動態(tài)規(guī)劃法動態(tài)規(guī)劃法2.5.近似算法近似算法2021/3/2737-1 問題概述問題概述 一、數(shù)學模型一、數(shù)學模型 1. 標準標準TSP 旅行商問題（簡稱旅行商問題（簡稱TSP）,也稱貨郎擔問題或也稱貨郎擔問題或旅行推銷員問題旅行推銷員問題,是運籌學中一個著名的問題，其一是運籌學中一個著名的問題，其一般提法為般提法為:有一個旅行商從城市有一個旅行商

2、從城市1出發(fā)，需要到城市出發(fā)，需要到城市2、3、n去推銷貨物，最后返回城市去推銷貨物，最后返回城市1，若任意，若任意兩個城市間的距離已知，則該旅行商應如何選擇其兩個城市間的距離已知，則該旅行商應如何選擇其最佳行走路線最佳行走路線?2021/3/274 TSP在圖論意義下又常常被稱為最小在圖論意義下又常常被稱為最小Hamilton圈問圈問題題,Euler等人最早研究了該問題的雛形等人最早研究了該問題的雛形,后來由英國的后來由英國的Hamilton爵士作為一個懸賞問題而提出。但這個能讓普通爵士作為一個懸賞問題而提出。但這個能讓普通人在幾分鐘內(nèi)就可理解的游戲之作，卻延續(xù)至今仍未能完全人在幾分鐘內(nèi)就可

3、理解的游戲之作，卻延續(xù)至今仍未能完全解決，成了一個世界難題。解決，成了一個世界難題。 TSP有著明顯的實際意義，如，郵局里負責到各信箱開有著明顯的實際意義，如，郵局里負責到各信箱開箱取信的郵遞員，以及去各分局送郵件的汽車等，都會遇到箱取信的郵遞員，以及去各分局送郵件的汽車等，都會遇到類似的問題。有趣的是，還有一些問題表面上看似乎與類似的問題。有趣的是，還有一些問題表面上看似乎與TSP無關，而實質(zhì)上卻可以歸結(jié)為無關，而實質(zhì)上卻可以歸結(jié)為TSP來求解。已經(jīng)證明，來求解。已經(jīng)證明，TSP是個是個NP難題，除非難題，除非P = NP，否則不存在有效算法。，否則不存在有效算法。2021/3/275 記為

4、賦權圖記為賦權圖G=(V,E),V為頂點集為頂點集,E為邊集，各為邊集，各頂點間的距離頂點間的距離dij已知。設已知。設1 ,0,iji jx若在回路路徑上其他則經(jīng)典的TSP可寫為如下的數(shù)學規(guī)劃模型:1111m in 1,(71)1,(72)s.t1, , 21 (73)0, 1nnijijijnijjnijiijiSjSijZd xxiVxjVxSSVSnx 2021/3/2761111min 1,(7 1)1,(7 2)s.t1, ,21 (7 3)0,1nnijijijnijjnijiiji S j SijZd xxiVxjVxSSVSnx 模型中模型中,為集合中所含圖的頂點數(shù)。約束（為

5、集合中所含圖的頂點數(shù)。約束（71）和（和（72）意味著對每個點而言）意味著對每個點而言,僅有一條邊進和一條僅有一條邊進和一條邊出邊出;約束（約束（73）則保證了沒有任何子回路解的產(chǎn)生。）則保證了沒有任何子回路解的產(chǎn)生。于是，滿足約束（于是，滿足約束（71）、（）、（72）和（）和（73）的解）的解構(gòu)成了一條構(gòu)成了一條Hamilton回路?；芈?。2021/3/277 當當dij=dji (i, jV) 時時,問題被稱為問題被稱為對稱型對稱型TSP,否否則稱為則稱為非對稱型非對稱型TSP。 若對所有若對所有1i, j, kn ，有不等式，有不等式dij + djk dik成立，則問題被稱為是成立，

6、則問題被稱為是滿足三角形不等式滿足三角形不等式的，簡稱的，簡稱為為TSP。2021/3/2782. 擴展擴展TSP(1) 瓶頸瓶頸TSP 瓶頸問題是最早從瓶頸問題是最早從TSP延伸出來的一種擴展型延伸出來的一種擴展型TSP,其含義與經(jīng)典的其含義與經(jīng)典的TSP類似類似,僅目標不同，要求僅目標不同，要求巡回路線中經(jīng)過的最長距離最短，即最小化瓶頸距巡回路線中經(jīng)過的最長距離最短，即最小化瓶頸距離。該情形體現(xiàn)了那些并不追求總巡回路線最短，離。該情形體現(xiàn)了那些并不追求總巡回路線最短，而只希望在巡回路線中每次從一個地點至另一個地而只希望在巡回路線中每次從一個地點至另一個地點的單次行程盡可能短的實際應用問題的

7、特征。點的單次行程盡可能短的實際應用問題的特征。2021/3/279 從嚴格的數(shù)學意義而言從嚴格的數(shù)學意義而言,瓶頸瓶頸TSP（簡稱（簡稱BTSP）并）并沒有降低問題的難度沒有降低問題的難度,也未能提供任何特殊的解決辦法。也未能提供任何特殊的解決辦法。 瓶頸瓶頸TSP的數(shù)學模型與標準的數(shù)學模型與標準TSP類似，僅目標函類似，僅目標函數(shù)不同數(shù)不同: min Zmax,ijijdxi jV 由于目標函數(shù)為瓶頸值由于目標函數(shù)為瓶頸值,故求得的最佳巡回路故求得的最佳巡回路線與標準線與標準TSP的往往截然不同。的往往截然不同。2021/3/2710(2) 最小比率最小比率TSP 最小比率最小比率TSP（

8、簡稱（簡稱MRTSP）是從經(jīng)典）是從經(jīng)典TSP引申出來的另一個變形問題引申出來的另一個變形問題,假定從一個城市走到另假定從一個城市走到另一個城市可得到某種收益（記為）一個城市可得到某種收益（記為）,則則MRTSP的目的目標就是確定最佳行走路線標就是確定最佳行走路線，使得回路的總行程與總，使得回路的總行程與總收益之比最小。這種優(yōu)化目標的思想類似于人們?nèi)帐找嬷茸钚　＿@種優(yōu)化目標的思想類似于人們?nèi)粘Ｉ钪薪?jīng)常使用的費用效益比，與單純的總行程常生活中經(jīng)常使用的費用效益比，與單純的總行程最短相比，往往更具實際意義。最短相比，往往更具實際意義。2021/3/2711 假定收益的數(shù)學性質(zhì)與相同假定收益的數(shù)

9、學性質(zhì)與相同,則最小比率則最小比率TSP的的數(shù)學模型也與標準數(shù)學模型也與標準TSP類似類似,僅目標函數(shù)不同僅目標函數(shù)不同: 毫無疑問毫無疑問,由于目標函數(shù)中的非線性因素由于目標函數(shù)中的非線性因素,最小最小比率比率TSP的求解比之標準的求解比之標準TSP顯得更為困難。顯得更為困難。m in ijijijijijijdxZpx2021/3/2712(3) 多人多人TSP 若標準若標準TSP中中,出發(fā)點有多個推銷員同時出發(fā)出發(fā)點有多個推銷員同時出發(fā),各自行走各自行走不同的路線，使得所有的城市都至少被訪問過一次，然后返不同的路線，使得所有的城市都至少被訪問過一次，然后返回出發(fā)點，要求所有推銷員的總行程

10、最短，則問題就成為一回出發(fā)點，要求所有推銷員的總行程最短，則問題就成為一個多人的旅行商問題（簡記個多人的旅行商問題（簡記MTSP）。）。 令決策變量令決策變量則則MTSP的數(shù)學模型為的數(shù)學模型為: 1,0,ijijx若有某推銷員從城市 到城市否則2021/3/2713-110-10-10min1,1, 2,1,01,1, 2,1. .,00,1,0,mnijijijnkjknikkijiiZd xjnxmjinxs tmixxi j 對對對對且 不 存 在 任 何 子 回 路 假定原問題為對稱型假定原問題為對稱型MTSP,V=v0,v1,vn-1,v0為名推銷員出發(fā)點，記為名推銷員出發(fā)點，記V

11、=v01,v02,v0m; v0,v1,vn-1 ，擴大的，擴大的m-1個頂點稱為個頂點稱為“人造頂點人造頂點”，其距離矩陣也相應擴大，其中，位于出發(fā)點的其距離矩陣也相應擴大，其中，位于出發(fā)點的m個個頂點相互間的距離設定為頂點相互間的距離設定為，其他數(shù)值不變。，其他數(shù)值不變。2021/3/2714二、多面體理論二、多面體理論 從上世紀從上世紀70年代開始的關于算法復雜性的研年代開始的關于算法復雜性的研究表明究表明,要想為要想為TSP找到一個好的算法找到一個好的算法,也即多項式也即多項式算法，似乎是不可能的。由于推銷員的每條路線可算法，似乎是不可能的。由于推銷員的每條路線可以用一個以以用一個以1

12、開始的排列來表示，因此所有可能的開始的排列來表示，因此所有可能的路線有條。這樣，若用枚舉法來解決這一問題，即路線有條。這樣，若用枚舉法來解決這一問題，即使不太大，例如使不太大，例如n30，用目前最快的計算機，也，用目前最快的計算機，也要化幾百萬年才能求出一條最短的路線。要化幾百萬年才能求出一條最短的路線。2021/3/2715 早在早在1954年年,Dantzig等人就曾提出過一種方等人就曾提出過一種方法（非多項式算法）法（非多項式算法）,并且求出了一個并且求出了一個42城市的城市的TSP最優(yōu)解。到了最優(yōu)解。到了1960年代，不少人用分支定界法解決年代，不少人用分支定界法解決了許多有幾十個城市

13、的了許多有幾十個城市的TSP。還有人提出了一些近。還有人提出了一些近似方法，也解決了許多有幾十個城市甚至上百個城似方法，也解決了許多有幾十個城市甚至上百個城市的市的TSP（有時找到的僅是近似解）。更值得注意（有時找到的僅是近似解）。更值得注意的是，從的是，從1970年代中期開始，年代中期開始，Grotschel與與Padberg等人深入研究了等人深入研究了TS多面體的最大面多面體的最大面（facet），并從所得結(jié)果出發(fā)獲得了一種解），并從所得結(jié)果出發(fā)獲得了一種解TSP的的新算法，可以解決一些有新算法，可以解決一些有100多個城市的多個城市的TSP，且，且都在不長的時間內(nèi)找到了最優(yōu)解。都在不長的

14、時間內(nèi)找到了最優(yōu)解。2021/3/2716 考慮個頂點的完全圖考慮個頂點的完全圖Kn ,則解則解TSP就相當于在就相當于在中求一條總長度最短的中求一條總長度最短的Hamilton回路?，F(xiàn)在回路。現(xiàn)在,對每對每條邊條邊ej，定義一個變量，定義一個變量xj與之對應，這樣，與之對應，這樣，TSP的一的一條路線條路線T，即，即Kn的一條的一條Hamilton回路，就可對應一回路，就可對應一個向量個向量X=x1,x2,.xm，其中，其中，1,0,jjjjxeTxeT若若2021/3/2717 稱稱X為路線為路線T的關聯(lián)向量的關聯(lián)向量,其其m=n(n-2)/2個分量中個分量中,恰好有恰好有個為個為1，其余

15、的都為，其余的都為0。 圖有許多圖有許多Hamilton回路，設為回路，設為T1, T2 Ts,，對應的關聯(lián)，對應的關聯(lián)向量記為向量記為X1, X2 Xs ，在，在m維空間維空間Rm中，考慮這些向量生成中，考慮這些向量生成的凸包（的凸包（convex hull） Qn :111,0,1,2,ssniiiiiiQXis2021/3/2718 Qn是是Rm中的一個凸多面體中的一個凸多面體,稱做稱做TS多面體。顯多面體。顯然然, Qn是有界的，其極點正好是是有界的，其極點正好是Kn的的Hamilton回路回路關聯(lián)向量。關聯(lián)向量。 研究研究Qn的面非常重要的，因為根據(jù)線性不等式的面非常重要的，因為根據(jù)

16、線性不等式及凸多面體的理論，及凸多面體的理論， Qn一定是某一個有限線性不一定是某一個有限線性不等式組的解集合，或者說，等式組的解集合，或者說， Qn一定是有限多個半一定是有限多個半空間的交。因此，如果能找出定義空間的交。因此，如果能找出定義Qn的線性不等式的線性不等式組來，就可將組來，就可將TSP作為一個線性規(guī)劃來解。作為一個線性規(guī)劃來解。2021/3/2719 TS多面體研究中的一個重要問題就是尋找能導出多面體研究中的一個重要問題就是尋找能導出Qn最大面的不等式最大面的不等式,Grotschel等人發(fā)現(xiàn)了一類很重要的能導等人發(fā)現(xiàn)了一類很重要的能導出最大面的梳子不等式出最大面的梳子不等式,并

17、予以了證明。此外，還有其它能并予以了證明。此外，還有其它能導出最大面的不等式，如團樹不等式等?？梢姡瑢С鲎畲竺娴牟坏仁?，如團樹不等式等?？梢?， Qn的最大的最大面極多，曾經(jīng)計算過由梳子不等式所導出的最大面?zhèn)€數(shù)如面極多，曾經(jīng)計算過由梳子不等式所導出的最大面?zhèn)€數(shù)如表表71所示所示:n6810203050120c(n)604142088419701.5*10181.5*103110602*10179表表71 2021/3/2720 可以看出可以看出,當增大時當增大時,最大面?zhèn)€數(shù)增長得非?？?。最大面?zhèn)€數(shù)增長得非?？?。 在在TS多面體理論的基礎上，可以考慮先解多面體理論的基礎上，可以考慮先解TSP的松弛

18、的松弛問題，如果得到的最優(yōu)解正好是某一條路線的關聯(lián)向量，那問題，如果得到的最優(yōu)解正好是某一條路線的關聯(lián)向量，那么就找到么就找到TSP的最優(yōu)解了的最優(yōu)解了;否則，就設法找一些新的不等式否則，就設法找一些新的不等式作為額外約束，再解新的線性規(guī)劃，直至找到恰好是關聯(lián)向作為額外約束，再解新的線性規(guī)劃，直至找到恰好是關聯(lián)向量的最優(yōu)解。這種做法的基本思想與解整數(shù)規(guī)劃的割平面法量的最優(yōu)解。這種做法的基本思想與解整數(shù)規(guī)劃的割平面法是同一類的，是同一類的，Gotschel 等人曾用這種方法解過有等人曾用這種方法解過有120個城個城市的市的TSP，所增加的不等式只有子回路消去不等式與梳子不，所增加的不等式只有子回

19、路消去不等式與梳子不等式兩類，在進行了等式兩類，在進行了13輪計算后，即解了輪計算后，即解了13個線性規(guī)劃后，個線性規(guī)劃后，就找到了就找到了TSP的精確最優(yōu)解，每一輪的當時計算時間僅在的精確最優(yōu)解，每一輪的當時計算時間僅在30秒至秒至2分鐘之間。有趣的是，當分鐘之間。有趣的是，當n = 120時，僅梳子不等式就時，僅梳子不等式就有有2*10179個，但在計算過程中，總共卻只（憑經(jīng)驗）添加個，但在計算過程中，總共卻只（憑經(jīng)驗）添加了了96個子回路消去不等式與梳子不等式。個子回路消去不等式與梳子不等式。2021/3/2721 當然當然,用該方法有時會用該方法有時會找不到找不到TSP的最優(yōu)解的最優(yōu)解

20、,因為很可能在進行了幾輪迭代后，卻找不到新的不因為很可能在進行了幾輪迭代后，卻找不到新的不等式。等式。Padborg與與Hong曾計算了曾計算了74個個TSP，其中，其中54個得到了最優(yōu)解，其余的雖未得到最優(yōu)解，卻得個得到了最優(yōu)解，其余的雖未得到最優(yōu)解，卻得到了很好的下界，如果與近似方法配合，可以估計到了很好的下界，如果與近似方法配合，可以估計近似解的精確程度。如，他們解過一個有近似解的精確程度。如，他們解過一個有313個城個城市的市的TSP，獲得一個下界，獲得一個下界41236.46，而用近似方法，而用近似方法能得到一條長為能得到一條長為41349的路線，于是可估計出所得的路線，于是可估計出

21、所得近似解與最優(yōu)解的誤差不超過近似解與最優(yōu)解的誤差不超過0.26%。2021/3/27227-2 求解算法求解算法一、下界和上界算法一、下界和上界算法1. 下界下界（1）下界）下界b1和和b2 針對針對TSP對應圖的鄰接矩陣對應圖的鄰接矩陣,將矩陣中每一行最小的元將矩陣中每一行最小的元素相加素相加,就可得到一個簡單的下界就可得到一個簡單的下界b1。經(jīng)進一步改進，可得。經(jīng)進一步改進，可得到更好的下界到更好的下界:考慮一個考慮一個TSP的完整解，在每條路徑上，每的完整解，在每條路徑上，每個城市都有兩條鄰接邊，一條進，一條出，那么，如果把矩個城市都有兩條鄰接邊，一條進，一條出，那么，如果把矩陣中每一

22、行最小的兩個元素相加再除以陣中每一行最小的兩個元素相加再除以2（不失一般性，可（不失一般性，可假定圖中所有距離權重都為整數(shù)），再對其結(jié)果向上取整，假定圖中所有距離權重都為整數(shù)），再對其結(jié)果向上取整，就可得到一個合理的下界就可得到一個合理的下界b2。 顯然，顯然，b2b1，因此，一般不采用，因此，一般不采用b1作為作為TSP的下界。的下界。2021/3/2723例例1 已知已知TSP及其距離矩陣如圖及其距離矩陣如圖71所示所示,試求其下試求其下界界 271563134253984(a) 無向圖無向圖圖圖71 無向圖無向圖及距離矩陣及距離矩陣(b) 距離矩陣距離矩陣3298347524519763

23、85132021/3/2724解解: 將矩陣中每一行最小的元素相加將矩陣中每一行最小的元素相加,1+3+1+3+2 = 10,即得即得b1=10。將矩陣中每一行最小的兩個元素相。將矩陣中每一行最小的兩個元素相加再除以加再除以2，再對結(jié)果向上取整，即可得，再對結(jié)果向上取整，即可得b2 = (1+3) + (3+6) + (1+2) + (3+4) + (2+3)/2 = 14。2021/3/2725（2）下界）下界b3為便于描述下界為便于描述下界b3,先定義如下符號先定義如下符號:T:對稱對稱TSP問題問題;n：結(jié)點總個數(shù)：結(jié)點總個數(shù);w(i,j)：結(jié)點：結(jié)點i與與j之間距離；之間距離；dmin

24、(i, k)：與第：與第i個結(jié)點關聯(lián)的所有邊中第個結(jié)點關聯(lián)的所有邊中第k (k = 1, 2, 3)長邊長邊的長度；的長度；dmin_j(i, k)：與第：與第i個結(jié)點關聯(lián)的所有邊中第個結(jié)點關聯(lián)的所有邊中第k (k = 1, 2, 3) 長長邊的另一個結(jié)點的編號邊的另一個結(jié)點的編號(其中一個結(jié)點編號為其中一個結(jié)點編號為i)；node_ base(i)= dmin_j(i, 1)+ dmin_j(i, 2)：表示與：表示與i點關聯(lián)邊點關聯(lián)邊中長度最短的兩條邊之和；中長度最短的兩條邊之和；C*(T)：最優(yōu)回路長度；：最優(yōu)回路長度；2021/3/2726 于是于是,dmin(i, 1)代表與第代表與

25、第i個結(jié)點關聯(lián)的所有邊個結(jié)點關聯(lián)的所有邊中最長邊的長度中最長邊的長度,dmin_j(i, 1) 代表與第代表與第i個結(jié)點關聯(lián)個結(jié)點關聯(lián)的所有邊中次長邊的另一個結(jié)點編號的所有邊中次長邊的另一個結(jié)點編號(其中一個結(jié)點其中一個結(jié)點編號為編號為i)，第，第i結(jié)點的結(jié)點的dmin(i, k)和和dmin_j(i, k)可由可由距離矩陣距離矩陣w輕易求得。輕易求得。 通過對下界通過對下界b2進行改進，可以得出一個求對稱進行改進，可以得出一個求對稱型型TSP更好的下界更好的下界b3。 在求在求b2的過程中，只有當與每一結(jié)點關聯(lián)的的過程中，只有當與每一結(jié)點關聯(lián)的邊中長度最小的兩條邊都出現(xiàn)在最優(yōu)邊中長度最小的兩

26、條邊都出現(xiàn)在最優(yōu)TSP回路中時，回路中時，等號才成立，下面就來分析如何提高這個下界。等號才成立，下面就來分析如何提高這個下界。2021/3/2727 對結(jié)點對結(jié)點i而言而言,設設e (i)1與與e (i)2分別為與結(jié)點分別為與結(jié)點i關關聯(lián)的邊中長度最小的兩條邊聯(lián)的邊中長度最小的兩條邊,其長度分別為其長度分別為dmin (i, 1) 和和dmin (i, 2)。 在對稱型在對稱型TSP回路中，由于有且僅有兩條邊與回路中，由于有且僅有兩條邊與每一結(jié)點關聯(lián)，因此，并不是與每個結(jié)點關聯(lián)的最每一結(jié)點關聯(lián)，因此，并不是與每個結(jié)點關聯(lián)的最小兩條邊都能出現(xiàn)在最優(yōu)小兩條邊都能出現(xiàn)在最優(yōu)TSP回路中，這意味可以回

27、路中，這意味可以在在node_ base(i)的基礎上增加的基礎上增加TSP回路的長度，將回路的長度，將在這種情況下增加的長度記為在這種情況下增加的長度記為Adjust (T)，現(xiàn)在分，現(xiàn)在分析如何計算析如何計算Adjust(T)。2021/3/2728 對結(jié)點對結(jié)點i的的e (i)1,邊邊e (i)1的一個結(jié)點為的一個結(jié)點為i,另一個另一個結(jié)點為結(jié)點為j = dmin_j (i,1)，若，若e (i)1也是結(jié)點也是結(jié)點j關聯(lián)邊中關聯(lián)邊中最小的兩條邊之一，即最小的兩條邊之一，即 i = dmin_j (j,1) 或或 i = dmin_j (j,2)，則對邊，則對邊e (i)1來說就不需要調(diào)整

28、，否來說就不需要調(diào)整，否則按以下方式調(diào)整則按以下方式調(diào)整:2021/3/2729若若e (i)1不是結(jié)點不是結(jié)點j=dmin_j(i,1)關聯(lián)邊中最小的兩條邊關聯(lián)邊中最小的兩條邊之一之一,則只有以下兩種情況則只有以下兩種情況: 選中選中e (i)1到到TSP回路中回路中 此時對結(jié)點此時對結(jié)點i不需調(diào)整不需調(diào)整,對結(jié)點對結(jié)點j來說，由于邊來說，由于邊e (i)1出現(xiàn)在最優(yōu)回路中，而出現(xiàn)在最優(yōu)回路中，而e (i)1不是結(jié)點不是結(jié)點j關聯(lián)邊中關聯(lián)邊中最小的兩條邊之一，因此會造成結(jié)點最小的兩條邊之一，因此會造成結(jié)點j關聯(lián)邊中最小關聯(lián)邊中最小的兩條邊中至少有一條不會出現(xiàn)在最優(yōu)回路中，從的兩條邊中至少有一

29、條不會出現(xiàn)在最優(yōu)回路中，從而對結(jié)點而對結(jié)點j而言，在而言，在node_base (i)的基礎上至少會的基礎上至少會增加的長度為增加的長度為 dmin (i,1) dmin (j,2) 。2021/3/2730 不選中不選中e (i)1到到TSP回路中回路中 此時對結(jié)點此時對結(jié)點i需要調(diào)整需要調(diào)整,由于邊由于邊e (i)1不在回路不在回路中中,故其在故其在node_base (i)的基礎上至少會增加的長的基礎上至少會增加的長度為度為 dmin (i,3) dmin (i,1)。 此時對結(jié)點此時對結(jié)點j來說，由于與它關聯(lián)的最短兩條來說，由于與它關聯(lián)的最短兩條邊仍然可能在回路中，因此不須調(diào)整。邊仍然

30、可能在回路中，因此不須調(diào)整。2021/3/2731 對于和對于和,必須有且僅有一種情況出現(xiàn)必須有且僅有一種情況出現(xiàn),現(xiàn)取兩種情現(xiàn)取兩種情況中增加長度小的值，因而回路的長路一定會在況中增加長度小的值，因而回路的長路一定會在b2的基礎上的基礎上增加增加:add_node (i,1) = 1/2*min (dmin (i,3) dmin (i,1), dmin (i,1) dmin (j,2)。 對結(jié)點對結(jié)點i的的e (i)2，邊，邊e (i)2的一個結(jié)點為的一個結(jié)點為i，另一個結(jié)點，另一個結(jié)點為為j = dmin_j (i,2)，若，若e (i)2也是結(jié)點也是結(jié)點j關聯(lián)邊中最小的兩條關聯(lián)邊中最小的

31、兩條邊之一，則對邊邊之一，則對邊e (i)2來說不需要調(diào)整，否則按與前面類似來說不需要調(diào)整，否則按與前面類似的方法計算調(diào)整值。經(jīng)分析，其在的方法計算調(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)。2021/3/2732 將每個結(jié)點都按上述方法進行一次調(diào)整將每個結(jié)點都按上述方法進行一次調(diào)整,其調(diào)其調(diào)整累加和就是整累加和就是Adjust (T),可寫成如下公式可寫成如下公式:1( )( 1)( 2)ni=Adjust Tadd_no

32、de i,+add_node i,2021/3/2733 將問題將問題T中所有結(jié)點的基本長度中所有結(jié)點的基本長度node_base(T)累加之和的一半稱為累加之和的一半稱為T的基本長度的基本長度,并用并用base (T)來來表示表示,可寫成如下公式可寫成如下公式:121( )1/2*( ,1)( ,2)1/2*( )ninibase Tdmin idmin inode_base ib2021/3/2734 于是于是,有有C*(T) base(T) + Adjust(T) = b3,即即 b3 = b2 + Adjust(T) 。由以上分析，不難得出求對稱由以上分析，不難得出求對稱TSP下界下界

33、b3的算法的算法:2021/3/2735Step 1. 計算計算base (T): get_base () i: Long For i = 1 To n base = base + dmin(i, 1) + dmin(i, 2) 2021/3/2736Step 2. 計算計算Adjust (T): get_adjust () i , ii1, ii2: Long For i = 1 To n ii1 = dmin_j (i, 1); ii2 = dmin_j (i, 2) If i dmin_j (ii1, 1) And i dmin_j (ii1, 2) adjust= adjust+min

34、(dmin(i, 3)-dmin(i,1), dmin(i, 1)-dmin(ii1, 2)If i dmin_j (ii2, 1) And i dmin_j (ii2, 2) adjust = adjust+min (dmin(i,3)-dmin(i, 2),dmin(i, 2)-dmin(ii2, 2) 2021/3/2737對例對例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)

35、=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) 無向圖無向圖圖圖71 無向圖無向圖2021/3/2738dmin(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)=

36、3；dmin(5, 2)=3；dmin_j(5, 2)=4；dmin(5, 3)=8；dmin_j(5, 3)=1；271563134253984(a) 無向圖無向圖圖圖71 無向圖無向圖52111/2*( )1/2*( ,1)( ,2)(13)(36)(12)(34)(23)/214niibnode_base idmin idmin i2021/3/2739add_node(1,1)=0; add_node(1,2)=0; add_node(2,1)=0; add_node(2,2)=1/2min (7-6), (6-2)=1/2;add_node(3,1)=0; add_node(3,2)

37、=1/2min (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。2021/3/27402. 上界上界 事實上事實上,TSP的任何可行解都是上界的任何可行解都是上界,這里，給這里，給出求出求TSP上界上界U1的貪心方法思想。的貪心方法思想。算法步驟如下算法步驟如下:2021/3/2741Step 1. 圖圖G = V, E中頂點個數(shù)為中頂點個數(shù)為n

38、 = |V|,邊的條數(shù)邊的條數(shù)m = |E|,令令i為出發(fā)點，為出發(fā)點，TSP_edge_n為加入到為加入到TSP回回路中邊的條數(shù)且路中邊的條數(shù)且TSP_edge_n = 0，TSP_edge為為已加入到已加入到TSP回路中的邊集合且回路中的邊集合且TSP_edge= ，k為為當前頂點當前頂點且且k = i。Step 2. 從邊集從邊集 中選中一條代價最小的一條邊中選中一條代價最小的一條邊(k, h),并執(zhí)行并執(zhí)行 TSP_edge_n = TSP_edge_n + 1; TSP_edge = TSP_edge + (k, h); k = h。Step 3. 若若TSP_edge_n U1,

39、故剪支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 = 02021/3/2749 (1)用貪心算法求得用貪心算法求得上界上界U1 = 16; (2)假定邊假定邊(1, 3)不在不在TSP回路中回路中,即即e13 = 0,此時，此時，b2 = (5+3) + (3+6) + (4+2) + (3+4) + (2+3)/2 = 17.5，由于由于b

40、2 = 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；2021/3/2750(4) 在在e12 = e13 = 1的情況下的情況下,由于頂點由于頂點1已有兩條關聯(lián)已有兩條關聯(lián)邊在最優(yōu)回路中邊在最優(yōu)回路中,因此在圖因此在圖71中中刪去刪去邊邊(1, 4

41、)和和(1, 5)，由于邊，由于邊(2, 3)與邊與邊(1, 2)、(1, 3)形成圈形成圈，因此在，因此在圖圖71中刪去邊中刪去邊(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;2021/3/2751(6)在在e12 =

42、 e13 = 1,e14 = e15 = e23 = e25 = 0的情況下的情況下,由由于與頂點于與頂點2關聯(lián)的邊有且只有關聯(lián)的邊有且只有2條在回路中，因此條在回路中，因此有有e24 = 1，進而有，進而有e35 = e54 = 1，e34 = 0。 至此，得到至此，得到 最優(yōu)解最優(yōu)解:e12 = e13 = e24 = e35 = e54 = 1，e14 = e15 = e23 = e25 = e34 = 0; 最優(yōu)目標值最優(yōu)目標值:1+2+3+7+3 = 16。 2021/3/27522. 基于降階的分支定界法基于降階的分支定界法 對于對于有向有向TSP的距離距陣的距離距陣,可通過不同情

43、況下可通過不同情況下上下界的對比來確定某些邊上下界的對比來確定某些邊(i, j)一定在或不在回路一定在或不在回路中。如果能確定中。如果能確定(i, j)一定在回路中一定在回路中,由于每個頂點分由于每個頂點分別別有且只有一條入邊和出邊有且只有一條入邊和出邊，從而可確定頂點，從而可確定頂點i的其的其它出邊一定不在回路中，也可以確定頂點它出邊一定不在回路中，也可以確定頂點j的其它出的其它出邊一定不在回路中，因此可將這些邊從距離距陣中邊一定不在回路中，因此可將這些邊從距離距陣中去掉，從而達到去掉，從而達到降低矩陣階數(shù)降低矩陣階數(shù)的目的。的目的。 這里，以一個具體的例子來予以說明。這里，以一個具體的例子

44、來予以說明。2021/3/2753例例2 已知有向已知有向TSP的距離矩陣如下的距離矩陣如下:6 5 4 3 2 165432192461888325338846287568090392816361745162142774933139332021/3/2754解解: 由于每個頂點都必須有一條入邊和出邊由于每個頂點都必須有一條入邊和出邊,因此因此將頂將頂點點i的所有出邊的權值減去所有出邊權值的最小值的所有出邊的權值減去所有出邊權值的最小值min_out(i),不會影響最優(yōu)解，僅最優(yōu)值在原來的基不會影響最優(yōu)解，僅最優(yōu)值在原來的基礎上減少了礎上減少了min_out (i)。 于是，可以將距離矩陣的每

45、一行和每一列都減于是，可以將距離矩陣的每一行和每一列都減去該行或該列的最小值，直至每行每列都含有去該行或該列的最小值，直至每行每列都含有0為為止。止。 將上述矩陣的每行分別減去該行的最小值將上述矩陣的每行分別減去該行的最小值3, 4, 16, 7, 25, 3，就得到如下縮減之后的矩陣，就得到如下縮減之后的矩陣:2021/3/27556 5 4 3 2 165432189431585008632130497383321202012912173873063010900 該縮減矩陣所對應該縮減矩陣所對應TSP的最優(yōu)解與原來的相同的最優(yōu)解與原來的相同,但最優(yōu)但最優(yōu)值比原來減少了值比原來減少了3+4+

46、16+7+25+3 = 58。 由于矩陣中第由于矩陣中第3、4列中不含列中不含0元素元素,因此可繼續(xù)縮減成因此可繼續(xù)縮減成:2021/3/2756該縮減矩陣所對應該縮減矩陣所對應TSP的最優(yōu)解與原來的相同的最優(yōu)解與原來的相同,但最優(yōu)但最優(yōu)值比原來減少了值比原來減少了3+4+16+7+25+3 = 58。由于矩陣中第由于矩陣中第3、4列中不含列中不含0元素元素,因此可繼續(xù)縮減成因此可繼續(xù)縮減成:2021/3/2757 其最優(yōu)值比原來減少其最優(yōu)值比原來減少58+15+8 = 81,這個這個81可可作為該作為該TSP初始的下界值初始的下界值b。6543216 5 4 3 2 189350850004

47、82130495883321201212912173058063027502021/3/2758按按e63 = 1和和e63 = 0將解分成兩種情況將解分成兩種情況:(1)e63 = 0 此時此時,邊邊(6, 3)不能出現(xiàn)在回路中不能出現(xiàn)在回路中,其權值在這其權值在這種情況下為種情況下為，因此，距離矩陣可修改為，因此，距離矩陣可修改為:893585000482130495883321201212912173058063027506 5 4 3 2 16543212021/3/2759 由于第由于第3列沒有列沒有0元素元素,故用第故用第3列各元素減去列各元素減去其最小元素其最小元素48,得如下縮

48、減矩陣得如下縮減矩陣:89358500002130491083321201212912173010063022706 5 4 3 2 1654321 此時的下界此時的下界 b = 81 + 48 = 129。2021/3/2760(2)e63 = 1 此時此時,邊邊(6, 3)已出現(xiàn)在回路中已出現(xiàn)在回路中,從頂點從頂點6出發(fā)的出發(fā)的其它邊都不可能在回路中，因此可其它邊都不可能在回路中，因此可刪去第刪去第6行行;同理，同理，進入到頂點進入到頂點3的其它邊都不可能在回路中，因此又的其它邊都不可能在回路中，因此又可可刪去第刪去第3列列。此時，邊。此時，邊(3, 6)不可能出現(xiàn)在回路中，不可能出現(xiàn)在回

49、路中，令邊令邊(3, 6)的權值為的權值為，矩陣化為，矩陣化為:0021304983320121291217300630206 5 4 2 1543212021/3/2761繼續(xù)依次計算繼續(xù)依次計算,并實施分支并實施分支和定界和定界,具體過程如圖具體過程如圖73所示所示:圖圖73 降階分支定界過程降階分支定界過程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的分

50、支剪去。2021/3/2762e63 = 1,e46 = 0下的縮減矩陣下的縮減矩陣: 00213175100121291217300630206 5 4 2 1543212021/3/2763e63 = e46 = 1下的縮減矩陣下的縮減矩陣:0213012917300302053215 4 2 12021/3/2764e63 = e46 = 1,e21 = 0下的縮減矩陣下的縮減矩陣:02100126013302053215 4 2 12021/3/2765e63 = e46 = e21 = 1下的縮減矩陣下的縮減矩陣:020002805315 4 22021/3/2766e63 = e4

51、6 = e21 = 1,e14 = 0下的縮減矩陣下的縮減矩陣:0200005315 4 22021/3/2767e63 = e46 = e21 = e14 = 1下的縮減矩陣下的縮減矩陣:2000535 22021/3/2768e63 = e46 = 1,e21 = e51 = 0下的縮減矩陣下的縮減矩陣:021010013302053215 4 2 12021/3/2769e63 = e46 = e51 =1,e21 = 0下的縮減矩陣下的縮減矩陣:01011003215 4 22021/3/2770e63 = e46 = e51 = 1,e21 = e14 = 0下的縮減矩陣下的縮減矩陣

52、:010003215 4 22021/3/2771e63 = e46 = e51 = e14 = 1,e21 = 0下的縮減矩陣下的縮減矩陣:000325 22021/3/2772 最后可得到兩個最優(yōu)最后可得到兩個最優(yōu)TSP回路回路:(1, 4, 6, 3, 2, 5, 1) 和和 (1, 4, 6, 3, 5, 2, 1),最優(yōu)回路長度為最優(yōu)回路長度為104。 若將無向圖中的每條邊看成有向圖中方向相反若將無向圖中的每條邊看成有向圖中方向相反的兩條邊的兩條邊,則無向圖也可看成是有向圖，因此，基于則無向圖也可看成是有向圖，因此，基于降階的分支定界法也可用來求解無向降階的分支定界法也可用來求解無向

53、TSP問題。問題。2021/3/2773三、動態(tài)規(guī)劃法定理定理1 TSP滿足滿足最優(yōu)性原理最優(yōu)性原理?？梢员硎鰹榭梢员硎鰹?“一個過程的最優(yōu)策一個過程的最優(yōu)策略具有這樣的性質(zhì)略具有這樣的性質(zhì),即無論初始狀態(tài)和初始決策如何即無論初始狀態(tài)和初始決策如何,對于先前決策所形成的狀態(tài)而言對于先前決策所形成的狀態(tài)而言,其以后的所有決策其以后的所有決策必構(gòu)成最優(yōu)策略必構(gòu)成最優(yōu)策略,”2021/3/2774證證: 設設s, s1, s2, , sp, s是從是從s出發(fā)的一條總長最短的出發(fā)的一條總長最短的簡單回路簡單回路,假設從假設從s到下一個城市到下一個城市s1已經(jīng)求出已經(jīng)求出,則問題則問題轉(zhuǎn)化為求從轉(zhuǎn)化為求

54、從s1到到s的最短路徑，顯然的最短路徑，顯然s1, s2, , sp, s一定構(gòu)成一條從一定構(gòu)成一條從s1到到s的最短路徑。若不然，設的最短路徑。若不然，設s1, r1, r2, , rq, s是一條從是一條從s1到到s的最短路徑且經(jīng)過的最短路徑且經(jīng)過n-1個不同城市，則個不同城市，則s, s1, r1, r2, , rq, s將是一條從將是一條從s出出發(fā)的路徑長度最短的簡單回路且比發(fā)的路徑長度最短的簡單回路且比s, s1, s2, , sp, s要短，從而導致矛盾。所以，要短，從而導致矛盾。所以，TSP滿足最優(yōu)性原滿足最優(yōu)性原理。理。2021/3/2775 設設TSP頂點編號分別為頂點編號分

55、別為0,1,2，n，假設從，假設從頂點頂點0出發(fā)，令出發(fā)，令d (i, V )表示從頂點表示從頂點 i 出發(fā)經(jīng)過出發(fā)經(jīng)過V 中中各頂點一次且僅一次，最后回到出發(fā)點各頂點一次且僅一次，最后回到出發(fā)點0的最短路的最短路徑長度，中間計算過程中的徑長度，中間計算過程中的d (k, Vk)也表示從也表示從頂點頂點 k 出發(fā)經(jīng)過出發(fā)經(jīng)過Vk 中各頂點一次且僅一次，中各頂點一次且僅一次，最后回到出發(fā)點最后回到出發(fā)點0（注意不是（注意不是k）的最短路徑長度。）的最短路徑長度。開始時，開始時，V = Vi，cij為頂點為頂點 i 至頂點至頂點 j 的距離，的距離，于是，于是，TSP的動態(tài)規(guī)劃遞推函數(shù)可寫成的動態(tài)

56、規(guī)劃遞推函數(shù)可寫成:2021/3/2776d (i, V ) = min cik + d (k, Vk) ( kV )d (k, ) = ck 0 ( k 0 )例例3 求解有向求解有向TSP:367523642375C2021/3/2777解解: 從城市從城市0出發(fā)經(jīng)城市出發(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 +

57、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é)果：這一階段的決策又依賴于下述計算結(jié)果：2021/3/2778d (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, )，

58、d (3, 1) = c31 + d (1, );而下式可以直接獲得（括號中是該決策引起的狀態(tài)轉(zhuǎn)而下式可以直接獲得（括號中是該決策引起的狀態(tài)轉(zhuǎn)移）移）:d (1, ) = c10 = 5 (10)，d (2, ) = c20 = 6 (20)，d (3, ) = c30 = 3 (30); 2021/3/2779再向前倒推再向前倒推,有有:d (1, 2) = c12 + d (2, ) = 2 + 6 = 8 (12),d (1, 3) = c13 + d (3, ) = 3 + 3 = 6 (13)， d (2, 3) = c23 + d (3, ) = 2 + 3 = 5 (23)，d

59、(2, 1) = c21 + d (1, ) = 4 + 5 = 9 (21)，d (3, 1) = c31 + d (1, ) = 7 + 5 = 12 (31)，d (3, 2) = c32 + d (2, ) = 5 + 6 = 11 (32);2021/3/2780再向前倒推再向前倒推,有有:d (1, 2, 3) = min c12 + d (2, 3), c13 + d (3, 2) = min 2+5, 3+11 = 7 (12),d (2, 1, 3) = min c21 + d (1, 3), c23 + d (3, 1) = min 4+6, 2+12 = 10 (21)，

60、d (3, 1, 2) = min c31 + d (1, 2), c32 + d (2, 1) = min 7+8, 5+9 = 14 (32); 2021/3/2781最后有最后有: 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 (01)。即即,從頂點從頂點0出發(fā)的出發(fā)的TSP最短回路長度為最短回路長度為10,回路路徑回路路徑為為:01230。2021/3/2782四、近似算法 由于精確式算法所能求解的問題規(guī)模非常有限由于精確式算