1第第7章章 旅行商問(wèn)題旅行商問(wèn)題2第第7章章 旅行商問(wèn)題旅行商問(wèn)題1.問(wèn)題概述問(wèn)題概述 2.求解算法求解算法 2.1.下界和上界算法下界和上界算法2.2.分支定界法分支定界法 目錄目錄2.5.競(jìng)賽題競(jìng)賽題2.3.動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法2.5.近似算法近似算法37-1 問(wèn)題概述問(wèn)題概述 一、數(shù)學(xué)模型一、數(shù)學(xué)模型 1. 標(biāo)準(zhǔn)標(biāo)準(zhǔn)TSP 旅行商問(wèn)題（簡(jiǎn)稱旅行商問(wèn)題（簡(jiǎn)稱TSP），也稱貨郎擔(dān)問(wèn)題或），也稱貨郎擔(dān)問(wèn)題或旅行推銷員問(wèn)題，是運(yùn)籌學(xué)中一個(gè)著名的問(wèn)題，其旅行推銷員問(wèn)題，是運(yùn)籌學(xué)中一個(gè)著名的問(wèn)題，其一般提法為：有一個(gè)旅行商從城市一般提法為：有一個(gè)旅行商從城市1出發(fā)，需要到出發(fā)，需要到城市城市2、3、n去推銷貨物，最后返回城市去推銷貨物，最后返回城市1，若，若任意兩個(gè)城市間的距離已知，則該旅行商應(yīng)如何選任意兩個(gè)城市間的距離已知，則該旅行商應(yīng)如何選擇其最佳行走路線？擇其最佳行走路線？4 TSP在圖論意義下又常常被稱為最小在圖論意義下又常常被稱為最小Hamilton圈問(wèn)題，圈問(wèn)題，Euler等人最早研究了該問(wèn)題的雛形，后來(lái)由英國(guó)的等人最早研究了該問(wèn)題的雛形，后來(lái)由英國(guó)的Hamilton爵士作為一個(gè)懸賞問(wèn)題而提出。但這個(gè)能讓普通人爵士作為一個(gè)懸賞問(wèn)題而提出。但這個(gè)能讓普通人在幾分鐘內(nèi)就可理解的游戲之作，卻延續(xù)至今仍未能完全解在幾分鐘內(nèi)就可理解的游戲之作，卻延續(xù)至今仍未能完全解決，成了一個(gè)世界難題。決，成了一個(gè)世界難題。 TSP有著明顯的實(shí)際意義，如，郵局里負(fù)責(zé)到各信箱開(kāi)有著明顯的實(shí)際意義，如，郵局里負(fù)責(zé)到各信箱開(kāi)箱取信的郵遞員，以及去各分局送郵件的汽車等，都會(huì)遇到箱取信的郵遞員，以及去各分局送郵件的汽車等，都會(huì)遇到類似的問(wèn)題。有趣的是，還有一些問(wèn)題表面上看似乎與類似的問(wèn)題。有趣的是，還有一些問(wèn)題表面上看似乎與TSP無(wú)關(guān)，而實(shí)質(zhì)上卻可以歸結(jié)為無(wú)關(guān)，而實(shí)質(zhì)上卻可以歸結(jié)為T(mén)SP來(lái)求解。已經(jīng)證明，來(lái)求解。已經(jīng)證明，TSP是個(gè)是個(gè)NP難題，除非難題，除非P = NP，否則不存在有效算法。，否則不存在有效算法。5 記為賦權(quán)圖記為賦權(quán)圖G=(V,E)，V為頂點(diǎn)集，為頂點(diǎn)集，E為邊集，為邊集，各頂點(diǎn)間的距離各頂點(diǎn)間的距離dij已知。設(shè)已知。設(shè)1 ,0,iji jx若在回路路徑上其他則經(jīng)典的TSP可寫(xiě)為如下的數(shù)學(xué)規(guī)劃模型：1111m in 1,(71)1,(72)s.t1, , 21 (73)0, 1nnijijijnijjnijiijiSjSijZd xxiVxjVxSSVSnx 61111min 1,(7 1)1,(7 2)s.t1, ,21 (7 3)0,1nnijijijnijjnijiiji S j SijZd xxiVxjVxSSVSnx 模型中，為集合中所含圖的頂點(diǎn)數(shù)。約束（模型中，為集合中所含圖的頂點(diǎn)數(shù)。約束（71）和（和（72）意味著對(duì)每個(gè)點(diǎn)而言，僅有一條邊進(jìn)和一條）意味著對(duì)每個(gè)點(diǎn)而言，僅有一條邊進(jìn)和一條邊出；約束（邊出；約束（73）則保證了沒(méi)有任何子回路解的產(chǎn)生。）則保證了沒(méi)有任何子回路解的產(chǎn)生。于是，滿足約束（于是，滿足約束（71）、（）、（72）和（）和（73）的解構(gòu)）的解構(gòu)成了一條成了一條Hamilton回路?；芈?。7 當(dāng)當(dāng)dij=dji (i, jV) 時(shí)，問(wèn)題被稱為時(shí)，問(wèn)題被稱為對(duì)稱型對(duì)稱型TSP，否，否則稱為則稱為非對(duì)稱型非對(duì)稱型TSP。 若對(duì)所有若對(duì)所有1i, j, kn ，有不等式，有不等式dij + djk dik成成立，則問(wèn)題被稱為是立，則問(wèn)題被稱為是滿足三角形不等式滿足三角形不等式的，簡(jiǎn)稱為的，簡(jiǎn)稱為T(mén)SP。82. 擴(kuò)展擴(kuò)展TSP(1) 瓶頸瓶頸TSP 瓶頸問(wèn)題是最早從瓶頸問(wèn)題是最早從TSP延伸出來(lái)的一種擴(kuò)展型延伸出來(lái)的一種擴(kuò)展型TSP，其含義與經(jīng)典的，其含義與經(jīng)典的TSP類似，僅目標(biāo)不同，要類似，僅目標(biāo)不同，要求巡回路線中經(jīng)過(guò)的最長(zhǎng)距離最短，即最小化瓶頸求巡回路線中經(jīng)過(guò)的最長(zhǎng)距離最短，即最小化瓶頸距離。該情形體現(xiàn)了那些并不追求總巡回路線最短，距離。該情形體現(xiàn)了那些并不追求總巡回路線最短，而只希望在巡回路線中每次從一個(gè)地點(diǎn)至另一個(gè)地而只希望在巡回路線中每次從一個(gè)地點(diǎn)至另一個(gè)地點(diǎn)的單次行程盡可能短的實(shí)際應(yīng)用問(wèn)題的特征。點(diǎn)的單次行程盡可能短的實(shí)際應(yīng)用問(wèn)題的特征。9 從嚴(yán)格的數(shù)學(xué)意義而言，瓶頸從嚴(yán)格的數(shù)學(xué)意義而言，瓶頸TSP（簡(jiǎn)稱（簡(jiǎn)稱BTSP）并沒(méi)有降低問(wèn)題的難度，也未能提供任何特殊的解決并沒(méi)有降低問(wèn)題的難度，也未能提供任何特殊的解決辦法。辦法。 瓶頸瓶頸TSP的數(shù)學(xué)模型與標(biāo)準(zhǔn)的數(shù)學(xué)模型與標(biāo)準(zhǔn)TSP類似，僅目標(biāo)函類似，僅目標(biāo)函數(shù)不同：數(shù)不同： min Zmax,ijijdxi jV 由于目標(biāo)函數(shù)為瓶頸值，故求得的最佳巡回路由于目標(biāo)函數(shù)為瓶頸值，故求得的最佳巡回路線與標(biāo)準(zhǔn)線與標(biāo)準(zhǔn)TSP的往往截然不同。的往往截然不同。10(2) 最小比率最小比率TSP 最小比率最小比率TSP（簡(jiǎn)稱（簡(jiǎn)稱MRTSP）是從經(jīng)典）是從經(jīng)典TSP引引申出來(lái)的另一個(gè)變形問(wèn)題申出來(lái)的另一個(gè)變形問(wèn)題，假定從一個(gè)城市走到另，假定從一個(gè)城市走到另一個(gè)城市可得到某種收益（記為），則一個(gè)城市可得到某種收益（記為），則MRTSP的的目標(biāo)就是確定最佳行走路線目標(biāo)就是確定最佳行走路線，使得回路的總行程與，使得回路的總行程與總收益之比最小。這種優(yōu)化目標(biāo)的思想類似于人們總收益之比最小。這種優(yōu)化目標(biāo)的思想類似于人們?nèi)粘Ｉ钪薪?jīng)常使用的費(fèi)用效益比，與單純的總行日常生活中經(jīng)常使用的費(fèi)用效益比，與單純的總行程最短相比，往往更具實(shí)際意義。程最短相比，往往更具實(shí)際意義。11 假定收益的數(shù)學(xué)性質(zhì)與相同，則最小比率假定收益的數(shù)學(xué)性質(zhì)與相同，則最小比率TSP的的數(shù)學(xué)模型也與標(biāo)準(zhǔn)數(shù)學(xué)模型也與標(biāo)準(zhǔn)TSP類似，僅目標(biāo)函數(shù)不同：類似，僅目標(biāo)函數(shù)不同： 毫無(wú)疑問(wèn)，由于目標(biāo)函數(shù)中的非線性因素，最毫無(wú)疑問(wèn)，由于目標(biāo)函數(shù)中的非線性因素，最小比率小比率TSP的求解比之標(biāo)準(zhǔn)的求解比之標(biāo)準(zhǔn)TSP顯得更為困難。顯得更為困難。m in ijijijijijijdxZpx12(3) 多人多人TSP 若標(biāo)準(zhǔn)若標(biāo)準(zhǔn)TSP中中，出發(fā)點(diǎn)有多個(gè)推銷員同時(shí)出發(fā)，各自行，出發(fā)點(diǎn)有多個(gè)推銷員同時(shí)出發(fā)，各自行走不同的路線，使得所有的城市都至少被訪問(wèn)過(guò)一次，然后走不同的路線，使得所有的城市都至少被訪問(wèn)過(guò)一次，然后返回出發(fā)點(diǎn)，要求所有推銷員的總行程最短，則問(wèn)題就成為返回出發(fā)點(diǎn)，要求所有推銷員的總行程最短，則問(wèn)題就成為一個(gè)多人的旅行商問(wèn)題（簡(jiǎn)記一個(gè)多人的旅行商問(wèn)題（簡(jiǎn)記MTSP）。）。 令決策變量令決策變量則則MTSP的數(shù)學(xué)模型為：的數(shù)學(xué)模型為： 1,0,ijijx若有某推銷員從城市 到城市否則13-110-10-10min1,1, 2,1,01,1, 2,1. .,00,1,0,mnijijijnkjknikkijiiZd xjnxmjinxs tmixxi j 對(duì)對(duì)對(duì)對(duì)且 不 存 在 任 何 子 回 路 假定原問(wèn)題為對(duì)稱型假定原問(wèn)題為對(duì)稱型MTSP，V=v0,v1,vn-1，v0為名推銷員出發(fā)點(diǎn)，記為名推銷員出發(fā)點(diǎn)，記V=v01,v02,v0m; v0,v1,vn-1 ，擴(kuò)大的，擴(kuò)大的m-1個(gè)頂點(diǎn)稱為個(gè)頂點(diǎn)稱為“人造頂點(diǎn)人造頂點(diǎn)”，其距離，其距離矩陣也相應(yīng)擴(kuò)大，其中，位于出發(fā)點(diǎn)的矩陣也相應(yīng)擴(kuò)大，其中，位于出發(fā)點(diǎn)的m個(gè)頂點(diǎn)相個(gè)頂點(diǎn)相互間的距離設(shè)定為互間的距離設(shè)定為，其他數(shù)值不變。，其他數(shù)值不變。14二、多面體理論二、多面體理論 從上世紀(jì)從上世紀(jì)70年代開(kāi)始的關(guān)于算法復(fù)雜性的研究年代開(kāi)始的關(guān)于算法復(fù)雜性的研究表明，要想為表明，要想為T(mén)SP找到一個(gè)好的算法，也即多項(xiàng)式找到一個(gè)好的算法，也即多項(xiàng)式算法，似乎是不可能的。由于推銷員的每條路線可算法，似乎是不可能的。由于推銷員的每條路線可以用一個(gè)以以用一個(gè)以1開(kāi)始的排列來(lái)表示，因此所有可能的開(kāi)始的排列來(lái)表示，因此所有可能的路線有條。這樣，若用枚舉法來(lái)解決這一問(wèn)題，即路線有條。這樣，若用枚舉法來(lái)解決這一問(wèn)題，即使不太大，例如使不太大，例如n30，用目前最快的計(jì)算機(jī)，也，用目前最快的計(jì)算機(jī)，也要化幾百萬(wàn)年才能求出一條最短的路線。要化幾百萬(wàn)年才能求出一條最短的路線。15 早在早在1954年，年，Dantzig等人就曾提出過(guò)一種方等人就曾提出過(guò)一種方法（非多項(xiàng)式算法），并且求出了一個(gè)法（非多項(xiàng)式算法），并且求出了一個(gè)42城市的城市的TSP最優(yōu)解。到了最優(yōu)解。到了1960年代，不少人用分支定界法年代，不少人用分支定界法解決了許多有幾十個(gè)城市的解決了許多有幾十個(gè)城市的TSP。還有人提出了一。還有人提出了一些近似方法，也解決了許多有幾十個(gè)城市甚至上百些近似方法，也解決了許多有幾十個(gè)城市甚至上百個(gè)城市的個(gè)城市的TSP（有時(shí)找到的僅是近似解）。更值得（有時(shí)找到的僅是近似解）。更值得注意的是，從注意的是，從1970年代中期開(kāi)始，年代中期開(kāi)始，Grotschel與與Padberg等人深入研究了等人深入研究了TS多面體的最大面多面體的最大面（facet），并從所得結(jié)果出發(fā)獲得了一種解），并從所得結(jié)果出發(fā)獲得了一種解TSP的的新算法，可以解決一些有新算法，可以解決一些有100多個(gè)城市的多個(gè)城市的TSP，且都，且都在不長(zhǎng)的時(shí)間內(nèi)找到了最優(yōu)解。在不長(zhǎng)的時(shí)間內(nèi)找到了最優(yōu)解。16 考慮個(gè)頂點(diǎn)的完全圖考慮個(gè)頂點(diǎn)的完全圖Kn ，則解，則解TSP就相當(dāng)于在就相當(dāng)于在中求一條總長(zhǎng)度最短的中求一條總長(zhǎng)度最短的Hamilton回路。現(xiàn)在，對(duì)每回路。現(xiàn)在，對(duì)每條邊條邊ej，定義一個(gè)變量，定義一個(gè)變量xj與之對(duì)應(yīng)，這樣，與之對(duì)應(yīng)，這樣，TSP的一的一條路線條路線T，即，即Kn的一條的一條Hamilton回路，就可對(duì)應(yīng)一回路，就可對(duì)應(yīng)一個(gè)向量個(gè)向量X=x1,x2,.xm，其中，其中，1,0,jjjjxeTxeT若若17 稱稱X為路線為路線T的關(guān)聯(lián)向量，其的關(guān)聯(lián)向量，其m=n(n-2)/2個(gè)分量中，恰好個(gè)分量中，恰好有個(gè)為有個(gè)為1，其余的都為，其余的都為0。 圖有許多圖有許多Hamilton回路，設(shè)為回路，設(shè)為T(mén)1, T2 Ts,，對(duì)應(yīng)的關(guān)聯(lián)向，對(duì)應(yīng)的關(guān)聯(lián)向量記為量記為X1, X2 Xs ，在，在m維空間維空間Rm中，考慮這些向量生成的中，考慮這些向量生成的凸包（凸包（convex hull） Qn ：111,0,1,2,ssniiiiiiQXis18 Qn是是Rm中的一個(gè)凸多面體，稱做中的一個(gè)凸多面體，稱做TS多面體。多面體。顯然，顯然， Qn是有界的，其極點(diǎn)正好是是有界的，其極點(diǎn)正好是Kn的的Hamilton回回路關(guān)聯(lián)向量。路關(guān)聯(lián)向量。 研究研究Qn的面非常重要的，因?yàn)楦鶕?jù)線性不等式的面非常重要的，因?yàn)楦鶕?jù)線性不等式及凸多面體的理論，及凸多面體的理論， Qn一定是某一個(gè)有限線性不等一定是某一個(gè)有限線性不等式組的解集合，或者說(shuō)，式組的解集合，或者說(shuō)， Qn一定是有限多個(gè)半空間一定是有限多個(gè)半空間的交。因此，如果能找出定義的交。因此，如果能找出定義Qn的線性不等式組來(lái)，的線性不等式組來(lái)，就可將就可將TSP作為一個(gè)線性規(guī)劃來(lái)解。作為一個(gè)線性規(guī)劃來(lái)解。19 TS多面體研究中的一個(gè)重要問(wèn)題就是尋找能導(dǎo)出多面體研究中的一個(gè)重要問(wèn)題就是尋找能導(dǎo)出Qn最大面的不等式，最大面的不等式，Grotschel等人發(fā)現(xiàn)了一類很重要的能導(dǎo)等人發(fā)現(xiàn)了一類很重要的能導(dǎo)出最大面的梳子不等式，并予以了證明。此外，還有其它出最大面的梳子不等式，并予以了證明。此外，還有其它能導(dǎo)出最大面的不等式，如團(tuán)樹(shù)不等式等。可見(jiàn)，能導(dǎo)出最大面的不等式，如團(tuán)樹(shù)不等式等。可見(jiàn)， Qn的最的最大面極多，曾經(jīng)計(jì)算過(guò)由梳子不等式所導(dǎo)出的最大面?zhèn)€數(shù)大面極多，曾經(jīng)計(jì)算過(guò)由梳子不等式所導(dǎo)出的最大面?zhèn)€數(shù)如表如表71所示：所示：n6810203050120c(n)604142088419701.5*10181.5*103110602*10179表表71 20 可以看出，當(dāng)增大時(shí)，最大面?zhèn)€數(shù)增長(zhǎng)得非?？臁？梢钥闯觯?dāng)增大時(shí)，最大面?zhèn)€數(shù)增長(zhǎng)得非?？?。 在在TS多面體理論的基礎(chǔ)上，可以考慮先解多面體理論的基礎(chǔ)上，可以考慮先解TSP的松弛問(wèn)的松弛問(wèn)題，如果得到的最優(yōu)解正好是某一條路線的關(guān)聯(lián)向量，那么題，如果得到的最優(yōu)解正好是某一條路線的關(guān)聯(lián)向量，那么就找到就找到TSP的最優(yōu)解了；否則，就設(shè)法找一些新的不等式作的最優(yōu)解了；否則，就設(shè)法找一些新的不等式作為額外約束，再解新的線性規(guī)劃，直至找到恰好是關(guān)聯(lián)向量為額外約束，再解新的線性規(guī)劃，直至找到恰好是關(guān)聯(lián)向量的最優(yōu)解。這種做法的基本思想與解整數(shù)規(guī)劃的割平面法是的最優(yōu)解。這種做法的基本思想與解整數(shù)規(guī)劃的割平面法是同一類的，同一類的，Gotschel 等人曾用這種方法解過(guò)有等人曾用這種方法解過(guò)有120個(gè)城市的個(gè)城市的TSP，所增加的不等式只有子回路消去不等式與梳子不等式，所增加的不等式只有子回路消去不等式與梳子不等式兩類，在進(jìn)行了兩類，在進(jìn)行了13輪計(jì)算后，即解了輪計(jì)算后，即解了13個(gè)線性規(guī)劃后，就找個(gè)線性規(guī)劃后，就找到了到了TSP的精確最優(yōu)解，每一輪的當(dāng)時(shí)計(jì)算時(shí)間僅在的精確最優(yōu)解，每一輪的當(dāng)時(shí)計(jì)算時(shí)間僅在30秒至秒至2分鐘之間。有趣的是，當(dāng)分鐘之間。有趣的是，當(dāng)n = 120時(shí)，僅梳子不等式就有時(shí)，僅梳子不等式就有2*10179個(gè)，但在計(jì)算過(guò)程中，總共卻只（憑經(jīng)驗(yàn)）添加了個(gè)，但在計(jì)算過(guò)程中，總共卻只（憑經(jīng)驗(yàn)）添加了96個(gè)子回路消去不等式與梳子不等式。個(gè)子回路消去不等式與梳子不等式。21 當(dāng)然，用該方法有時(shí)會(huì)當(dāng)然，用該方法有時(shí)會(huì)找不到找不到TSP的最優(yōu)解，的最優(yōu)解，因?yàn)楹芸赡茉谶M(jìn)行了幾輪迭代后，卻找不到新的不因?yàn)楹芸赡茉谶M(jìn)行了幾輪迭代后，卻找不到新的不等式。等式。Padborg與與Hong曾計(jì)算了曾計(jì)算了74個(gè)個(gè)TSP，其中，其中54個(gè)得到了最優(yōu)解，其余的雖未得到最優(yōu)解，卻得到個(gè)得到了最優(yōu)解，其余的雖未得到最優(yōu)解，卻得到了很好的下界，如果與近似方法配合，可以估計(jì)近了很好的下界，如果與近似方法配合，可以估計(jì)近似解的精確程度。如，他們解過(guò)一個(gè)有似解的精確程度。如，他們解過(guò)一個(gè)有313個(gè)城市個(gè)城市的的TSP，獲得一個(gè)下界，獲得一個(gè)下界41236.46，而用近似方法能，而用近似方法能得到一條長(zhǎng)為得到一條長(zhǎng)為41349的路線，于是可估計(jì)出所得近的路線，于是可估計(jì)出所得近似解與最優(yōu)解的誤差不超過(guò)似解與最優(yōu)解的誤差不超過(guò)0.26%。227-2 求解算法求解算法一、下界和上界算法一、下界和上界算法1. 下界下界（1）下界）下界b1和和b2 針對(duì)針對(duì)TSP對(duì)應(yīng)圖的鄰接矩陣，將矩陣中每一行最小的元對(duì)應(yīng)圖的鄰接矩陣，將矩陣中每一行最小的元素相加，就可得到一個(gè)簡(jiǎn)單的下界素相加，就可得到一個(gè)簡(jiǎn)單的下界b1。經(jīng)進(jìn)一步改進(jìn)，可得。經(jīng)進(jìn)一步改進(jìn)，可得到更好的下界：考慮一個(gè)到更好的下界：考慮一個(gè)TSP的完整解，在每條路徑上，每的完整解，在每條路徑上，每個(gè)城市都有兩條鄰接邊，一條進(jìn)，一條出，那么，如果把矩個(gè)城市都有兩條鄰接邊，一條進(jìn)，一條出，那么，如果把矩陣中每一行最小的兩個(gè)元素相加再除以陣中每一行最小的兩個(gè)元素相加再除以2（不失一般性，可（不失一般性，可假定圖中所有距離權(quán)重都為整數(shù)），再對(duì)其結(jié)果向上取整，假定圖中所有距離權(quán)重都為整數(shù)），再對(duì)其結(jié)果向上取整，就可得到一個(gè)合理的下界就可得到一個(gè)合理的下界b2。 顯然，顯然，b2b1，因此，一般不采用，因此，一般不采用b1作為作為T(mén)SP的下界。的下界。23例例1 已知已知TSP及其距離矩陣如圖及其距離矩陣如圖71所示，試求其下所示，試求其下界界 271563134253984(a) 無(wú)向圖無(wú)向圖圖圖71 無(wú)向圖及無(wú)向圖及距離矩陣距離矩陣(b) 距離矩陣距離矩陣3298347524519763851324解：解： 將矩陣中每一行最小的元素相加，將矩陣中每一行最小的元素相加，1+3+1+3+2 = 10，即得，即得b1=10。將矩陣中每一行最小的兩個(gè)元素相。將矩陣中每一行最小的兩個(gè)元素相加再除以加再除以2，再對(duì)結(jié)果向上取整，即可得，再對(duì)結(jié)果向上取整，即可得b2 = (1+3) + (3+6) + (1+2) + (3+4) + (2+3)/2 = 14。25（2）下界）下界b3為便于描述下界為便于描述下界b3，先定義如下符號(hào)：，先定義如下符號(hào)：T：對(duì)稱：對(duì)稱TSP問(wèn)題；問(wèn)題；n：結(jié)點(diǎn)總個(gè)數(shù)；：結(jié)點(diǎn)總個(gè)數(shù)；w(i,j)：結(jié)點(diǎn)：結(jié)點(diǎn)i與與j之間距離；之間距離；dmin(i, k)：與第：與第i個(gè)結(jié)點(diǎn)關(guān)聯(lián)的所有邊中第個(gè)結(jié)點(diǎn)關(guān)聯(lián)的所有邊中第k (k = 1, 2, 3)長(zhǎng)邊的長(zhǎng)邊的長(zhǎng)度；長(zhǎng)度；dmin_j(i, k)：與第：與第i個(gè)結(jié)點(diǎn)關(guān)聯(lián)的所有邊中第個(gè)結(jié)點(diǎn)關(guān)聯(lián)的所有邊中第k (k = 1, 2, 3) 長(zhǎng)邊長(zhǎng)邊的另一個(gè)結(jié)點(diǎn)的編號(hào)的另一個(gè)結(jié)點(diǎn)的編號(hào)(其中一個(gè)結(jié)點(diǎn)編號(hào)為其中一個(gè)結(jié)點(diǎn)編號(hào)為i)；node_ base(i)= dmin_j(i, 1)+ dmin_j(i, 2)：表示與：表示與i點(diǎn)關(guān)聯(lián)邊中長(zhǎng)點(diǎn)關(guān)聯(lián)邊中長(zhǎng)度最短的兩條邊之和；度最短的兩條邊之和；C*(T)：最優(yōu)回路長(zhǎng)度；：最優(yōu)回路長(zhǎng)度；26 于是，于是，dmin(i, 1)代表與第代表與第i個(gè)結(jié)點(diǎn)關(guān)聯(lián)的所有邊個(gè)結(jié)點(diǎn)關(guān)聯(lián)的所有邊中最長(zhǎng)邊的長(zhǎng)度，中最長(zhǎng)邊的長(zhǎng)度，dmin_j(i, 1) 代表與第代表與第i個(gè)結(jié)點(diǎn)關(guān)聯(lián)個(gè)結(jié)點(diǎn)關(guān)聯(lián)的所有邊中次長(zhǎng)邊的另一個(gè)結(jié)點(diǎn)編號(hào)的所有邊中次長(zhǎng)邊的另一個(gè)結(jié)點(diǎn)編號(hào)(其中一個(gè)結(jié)點(diǎn)其中一個(gè)結(jié)點(diǎn)編號(hào)為編號(hào)為i)，第，第i結(jié)點(diǎn)的結(jié)點(diǎn)的dmin(i, k)和和dmin_j(i, k)可由距可由距離矩陣離矩陣w輕易求得。輕易求得。 通過(guò)對(duì)下界通過(guò)對(duì)下界b2進(jìn)行改進(jìn)，可以得出一個(gè)求對(duì)稱進(jìn)行改進(jìn)，可以得出一個(gè)求對(duì)稱型型TSP更好的下界更好的下界b3。 在求在求b2的過(guò)程中，只有當(dāng)與每一結(jié)點(diǎn)關(guān)聯(lián)的邊的過(guò)程中，只有當(dāng)與每一結(jié)點(diǎn)關(guān)聯(lián)的邊中長(zhǎng)度最小的兩條邊都出現(xiàn)在最優(yōu)中長(zhǎng)度最小的兩條邊都出現(xiàn)在最優(yōu)TSP回路中時(shí)，回路中時(shí)，等號(hào)才成立，下面就來(lái)分析如何提高這個(gè)下界。等號(hào)才成立，下面就來(lái)分析如何提高這個(gè)下界。27 對(duì)結(jié)點(diǎn)對(duì)結(jié)點(diǎn)i而言，設(shè)而言，設(shè)e (i)1與與e (i)2分別為與結(jié)點(diǎn)分別為與結(jié)點(diǎn)i關(guān)關(guān)聯(lián)的邊中長(zhǎng)度最小的兩條邊，其長(zhǎng)度分別為聯(lián)的邊中長(zhǎng)度最小的兩條邊，其長(zhǎng)度分別為dmin (i, 1) 和和dmin (i, 2)。 在對(duì)稱型在對(duì)稱型TSP回路中，由于有且僅有兩條邊與回路中，由于有且僅有兩條邊與每一結(jié)點(diǎn)關(guān)聯(lián)，因此，并不是與每個(gè)結(jié)點(diǎn)關(guān)聯(lián)的最每一結(jié)點(diǎn)關(guān)聯(lián)，因此，并不是與每個(gè)結(jié)點(diǎn)關(guān)聯(lián)的最小兩條邊都能出現(xiàn)在最優(yōu)小兩條邊都能出現(xiàn)在最優(yōu)TSP回路中，這意味可以回路中，這意味可以在在node_ base(i)的基礎(chǔ)上增加的基礎(chǔ)上增加TSP回路的長(zhǎng)度，將在回路的長(zhǎng)度，將在這種情況下增加的長(zhǎng)度記為這種情況下增加的長(zhǎng)度記為Adjust (T)，現(xiàn)在分析，現(xiàn)在分析如何計(jì)算如何計(jì)算Adjust(T)。28 對(duì)結(jié)點(diǎn)對(duì)結(jié)點(diǎn)i的的e (i)1，邊，邊e (i)1的一個(gè)結(jié)點(diǎn)為的一個(gè)結(jié)點(diǎn)為i，另一，另一個(gè)結(jié)點(diǎn)為個(gè)結(jié)點(diǎn)為j = dmin_j (i,1)，若，若e (i)1也是結(jié)點(diǎn)也是結(jié)點(diǎn)j關(guān)聯(lián)邊關(guān)聯(lián)邊中最小的兩條邊之一，即中最小的兩條邊之一，即 i = dmin_j (j,1) 或或 i = dmin_j (j,2)，則對(duì)邊，則對(duì)邊e (i)1來(lái)說(shuō)就不需要調(diào)整，否則來(lái)說(shuō)就不需要調(diào)整，否則按以下方式調(diào)整：按以下方式調(diào)整：29若若e (i)1不是結(jié)點(diǎn)不是結(jié)點(diǎn)j=dmin_j(i,1)關(guān)聯(lián)邊中最小的兩條邊關(guān)聯(lián)邊中最小的兩條邊之一，則只有以下兩種情況：之一，則只有以下兩種情況： 選中選中e (i)1到到TSP回路中回路中 此時(shí)對(duì)結(jié)點(diǎn)此時(shí)對(duì)結(jié)點(diǎn)i不需調(diào)整，對(duì)結(jié)點(diǎn)不需調(diào)整，對(duì)結(jié)點(diǎn)j來(lái)說(shuō)，由于邊來(lái)說(shuō)，由于邊e (i)1出現(xiàn)在最優(yōu)回路中，而出現(xiàn)在最優(yōu)回路中，而e (i)1不是結(jié)點(diǎn)不是結(jié)點(diǎn)j關(guān)聯(lián)邊關(guān)聯(lián)邊中最小的兩條邊之一，因此會(huì)造成結(jié)點(diǎn)中最小的兩條邊之一，因此會(huì)造成結(jié)點(diǎn)j關(guān)聯(lián)邊中最關(guān)聯(lián)邊中最小的兩條邊中至少有一條不會(huì)出現(xiàn)在最優(yōu)回路中，小的兩條邊中至少有一條不會(huì)出現(xiàn)在最優(yōu)回路中，從而對(duì)結(jié)點(diǎn)從而對(duì)結(jié)點(diǎn)j而言，在而言，在node_base (i)的基礎(chǔ)上至少會(huì)的基礎(chǔ)上至少會(huì)增加的長(zhǎng)度為增加的長(zhǎng)度為 dmin (i,1) dmin (j,2) 。30 不選中不選中e (i)1到到TSP回路中回路中 此時(shí)對(duì)結(jié)點(diǎn)此時(shí)對(duì)結(jié)點(diǎn)i需要調(diào)整，由于邊需要調(diào)整，由于邊e (i)1不在回路不在回路中，故其在中，故其在node_base (i)的基礎(chǔ)上至少會(huì)增加的長(zhǎng)的基礎(chǔ)上至少會(huì)增加的長(zhǎng)度為度為 dmin (i,3) dmin (i,1)。 此時(shí)對(duì)結(jié)點(diǎn)此時(shí)對(duì)結(jié)點(diǎn)j來(lái)說(shuō)，由于與它關(guān)聯(lián)的最短兩條邊來(lái)說(shuō)，由于與它關(guān)聯(lián)的最短兩條邊仍然可能在回路中，因此不須調(diào)整。仍然可能在回路中，因此不須調(diào)整。31 對(duì)于和，必須有且僅有一種情況出現(xiàn)，現(xiàn)取兩種對(duì)于和，必須有且僅有一種情況出現(xiàn)，現(xiàn)取兩種情況中增加長(zhǎng)度小的值，因而回路的長(zhǎng)路一定會(huì)在情況中增加長(zhǎng)度小的值，因而回路的長(zhǎng)路一定會(huì)在b2的基礎(chǔ)的基礎(chǔ)上增加：上增加：add_node (i,1) = 1/2*min (dmin (i,3) dmin (i,1), dmin (i,1) dmin (j,2)。 對(duì)結(jié)點(diǎn)對(duì)結(jié)點(diǎn)i的的e (i)2，邊，邊e (i)2的一個(gè)結(jié)點(diǎn)為的一個(gè)結(jié)點(diǎn)為i，另一個(gè)結(jié)點(diǎn)為，另一個(gè)結(jié)點(diǎn)為j = dmin_j (i,2)，若，若e (i)2也是結(jié)點(diǎn)也是結(jié)點(diǎn)j關(guān)聯(lián)邊中最小的兩條邊之一，關(guān)聯(lián)邊中最小的兩條邊之一，則對(duì)邊則對(duì)邊e (i)2來(lái)說(shuō)不需要調(diào)整，否則按與前面類似的方法計(jì)算來(lái)說(shuō)不需要調(diào)整，否則按與前面類似的方法計(jì)算調(diào)整值。經(jīng)分析，其在調(diào)整值。經(jīng)分析，其在base (T)的基礎(chǔ)上至少要增加：的基礎(chǔ)上至少要增加：add_node (i,2) = 1/2*min (dmin (i,3) dmin (i,2), dmin (i,2) dmin (j,2)。32 將每個(gè)結(jié)點(diǎn)都按上述方法進(jìn)行一次調(diào)整，其調(diào)將每個(gè)結(jié)點(diǎn)都按上述方法進(jìn)行一次調(diào)整，其調(diào)整累加和就是整累加和就是Adjust (T)，可寫(xiě)成如下公式：，可寫(xiě)成如下公式：1( )( 1)( 2)ni=Adjust Tadd_node i,+add_node i,33 將問(wèn)題將問(wèn)題T中所有結(jié)點(diǎn)的基本長(zhǎng)度中所有結(jié)點(diǎn)的基本長(zhǎng)度node_base(T)累累加之和的一半稱為加之和的一半稱為T(mén)的基本長(zhǎng)度，并用的基本長(zhǎng)度，并用base (T)來(lái)表來(lái)表示，可寫(xiě)成如下公式：示，可寫(xiě)成如下公式：121( )1/2*( ,1)( ,2)1/2*( )ninibase Tdmin idmin inode_base ib34 于是，有于是，有C*(T) base(T) + Adjust(T) = b3，即，即 b3 = b2 + Adjust(T) 。由以上分析，不難得出求對(duì)稱由以上分析，不難得出求對(duì)稱TSP下界下界b3的算法：的算法：35Step 1. 計(jì)算計(jì)算base (T)： get_base () i: Long For i = 1 To n base = base + dmin(i, 1) + dmin(i, 2) 36Step 2. 計(jì)算計(jì)算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(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) 37對(duì)例對(duì)例1而言，可計(jì)算其而言，可計(jì)算其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) 無(wú)向圖無(wú)向圖圖圖71 無(wú)向圖無(wú)向圖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) 無(wú)向圖無(wú)向圖圖圖71 無(wú)向圖無(wú)向圖52111/2*( )1/2*( ,1)( ,2)(13)(36)(12)(34)(23)/214niibnode_base idmin idmin i39add_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)=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。402. 上界上界 事實(shí)上，事實(shí)上，TSP的任何可行解都是上界，這里，的任何可行解都是上界，這里，給出求給出求TSP上界上界U1的貪心方法思想。的貪心方法思想。算法步驟如下：算法步驟如下：41Step 1. 圖圖G = V, E中頂點(diǎn)個(gè)數(shù)為中頂點(diǎn)個(gè)數(shù)為n = |V|，邊的條數(shù)，邊的條數(shù)m = |E|，令，令i為出發(fā)點(diǎn)，為出發(fā)點(diǎn)，TSP_edge_n為加入到為加入到TSP回路回路中邊的條數(shù)且中邊的條數(shù)且TSP_edge_n = 0，TSP_edge為已加入為已加入到到TSP回路中的邊集合且回路中的邊集合且TSP_edge= ，k為為當(dāng)前頂當(dāng)前頂點(diǎn)點(diǎn)且且k = i。Step 2. 從邊集從邊集 中選中一條代價(jià)最小的一條邊中選中一條代價(jià)最小的一條邊(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, 故剪支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, 故剪支此時(shí)有e14=e15= e23=0此時(shí)有e24= e35= e54=1, e34 = 049 (1)用貪心算法求得用貪心算法求得上界上界U1 = 16； (2)假定邊假定邊(1, 3)不在不在TSP回路中回路中，即，即e13 = 0，此時(shí)，此時(shí)，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，此時(shí)，此時(shí)b2 = (1+5) + (6+7) + (1+2) + (3+4) + (2+3)/2 = 17，由于，由于b2 = 17 U1 = 16，因此邊，因此邊(1, 2)一定在回路中，即一定在回路中，即e12 = 1；50(4) 在在e12 = e13 = 1的情況下，由于頂點(diǎn)的情況下，由于頂點(diǎn)1已有兩條關(guān)聯(lián)已有兩條關(guān)聯(lián)邊在最優(yōu)回路中，因此在圖邊在最優(yōu)回路中，因此在圖71中中刪去刪去邊邊(1, 4)和和(1, 5)，由于邊，由于邊(2, 3)與邊與邊(1, 2)、(1, 3)形成圈形成圈，因此，因此在圖在圖71中刪去邊中刪去邊(2, 3)，即此時(shí)，即此時(shí)e14 = e15 = e23 = 0；(5)在在e12 = e13 = 1，e14 = e15 = e23 = 0的情況下，的情況下，假定假定e25 = 1，此時(shí)，此時(shí)b2 = (1+3) + (3+9) + (1+2) + (3+4) + (2+9)/2 = 18.5，由于，由于b2 = 18.5 U1 = 16，因此邊，因此邊(2, 5)一定不在回路中，即一定不在回路中，即e25 = 0；51(6)在在e12 = e13 = 1，e14 = e15 = e23 = e25 = 0的情況下，由的情況下，由于與頂點(diǎn)于與頂點(diǎn)2關(guān)聯(lián)的邊有且只有關(guān)聯(lián)的邊有且只有2條在回路中，因此條在回路中，因此有有e24 = 1，進(jìn)而有，進(jìn)而有e35 = e54 = 1，e34 = 0。 至此，得到至此，得到 最優(yōu)解：最優(yōu)解：e12 = e13 = e24 = e35 = e54 = 1，e14 = e15 = e23 = e25 = e34 = 0； 最優(yōu)目標(biāo)值：最優(yōu)目標(biāo)值：1+2+3+7+3 = 16。 522. 基于降階的分支定界法基于降階的分支定界法 對(duì)于對(duì)于有向有向TSP的距離距陣，可通過(guò)不同情況下的距離距陣，可通過(guò)不同情況下上下界的對(duì)比來(lái)確定某些邊上下界的對(duì)比來(lái)確定某些邊(i, j)一定在或不在回路一定在或不在回路中。如果能確定中。如果能確定(i, j)一定在回路中，由于每個(gè)頂點(diǎn)一定在回路中，由于每個(gè)頂點(diǎn)分別分別有且只有一條入邊和出邊有且只有一條入邊和出邊，從而可確定頂點(diǎn)，從而可確定頂點(diǎn)i的的其它出邊一定不在回路中，也可以確定頂點(diǎn)其它出邊一定不在回路中，也可以確定頂點(diǎn)j的其它的其它出邊一定不在回路中，因此可將這些邊從距離距陣出邊一定不在回路中，因此可將這些邊從距離距陣中去掉，從而達(dá)到中去掉，從而達(dá)到降低矩陣階數(shù)降低矩陣階數(shù)的目的。的目的。 這里，以一個(gè)具體的例子來(lái)予以說(shuō)明。這里，以一個(gè)具體的例子來(lái)予以說(shuō)明。53例例2 已知有向已知有向TSP的距離矩陣如下：的距離矩陣如下：6 5 4 3 2 1654321924618883253388462875680903928163617451621427749331393354解解: 由于每個(gè)頂點(diǎn)都必須有一條入邊和出邊，因此由于每個(gè)頂點(diǎn)都必須有一條入邊和出邊，因此將將頂點(diǎn)頂點(diǎn)i的所有出邊的權(quán)值減去所有出邊權(quán)值的最小值的所有出邊的權(quán)值減去所有出邊權(quán)值的最小值min_out(i)，不會(huì)影響最優(yōu)解，僅最優(yōu)值在原來(lái)的基，不會(huì)影響最優(yōu)解，僅最優(yōu)值在原來(lái)的基礎(chǔ)上減少了礎(chǔ)上減少了min_out (i)。 于是，可以將距離矩陣的每一行和每一列都減于是，可以將距離矩陣的每一行和每一列都減去該行或該列的最小值，直至每行每列都含有去該行或該列的最小值，直至每行每列都含有0為為止。止。 將上述矩陣的每行分別減去該行的最小值將上述矩陣的每行分別減去該行的最小值3, 4, 16, 7, 25, 3，就得到如下縮減之后的矩陣：，就得到如下縮減之后的矩陣：556 5 4 3 2 165432189431585008632130497383321202012912173873063010900 該縮減矩陣所對(duì)應(yīng)該縮減矩陣所對(duì)應(yīng)TSP的最優(yōu)解與原來(lái)的相同，但最優(yōu)的最優(yōu)解與原來(lái)的相同，但最優(yōu)值比原來(lái)減少了值比原來(lái)減少了3+4+16+7+25+3 = 58。 由于矩陣中第由于矩陣中第3、4列中不含列中不含0元素，因此可繼續(xù)縮減成：元素，因此可繼續(xù)縮減成：56該縮減矩陣所對(duì)應(yīng)該縮減矩陣所對(duì)應(yīng)TSP的最優(yōu)解與原來(lái)的相同，但最的最優(yōu)解與原來(lái)的相同，但最優(yōu)值比原來(lái)減少了優(yōu)值比原來(lái)減少了3+4+16+7+25+3 = 58。由于矩陣中第由于矩陣中第3、4列中不含列中不含0元素，因此可繼續(xù)縮減元素，因此可繼續(xù)縮減成：成：57 其最優(yōu)值比原來(lái)減少其最優(yōu)值比原來(lái)減少58+15+8 = 81，這個(gè)，這個(gè)81可可作為該作為該TSP初始的下界值初始的下界值b。6543216 5 4 3 2 189350850004821304958833212012129121730580630275058按按e63 = 1和和e63 = 0將解分成兩種情況：將解分成兩種情況：(1)e63 = 0 此時(shí)，邊此時(shí)，邊(6, 3)不能出現(xiàn)在回路中，其權(quán)值在不能出現(xiàn)在回路中，其權(quán)值在這種情況下為這種情況下為，因此，距離矩陣可修改為：，因此，距離矩陣可修改為：893585000482130495883321201212912173058063027506 5 4 3 2 165432159 由于第由于第3列沒(méi)有列沒(méi)有0元素，故用第元素，故用第3列各元素減去列各元素減去其最小元素其最小元素48，得如下縮減矩陣：，得如下縮減矩陣：89358500002130491083321201212912173010063022706 5 4 3 2 1654321 此時(shí)的下界此時(shí)的下界 b = 81 + 48 = 129。60(2)e63 = 1 此時(shí)，邊此時(shí)，邊(6, 3)已出現(xiàn)在回路中，從頂點(diǎn)已出現(xiàn)在回路中，從頂點(diǎn)6出發(fā)出發(fā)的其它邊都不可能在回路中，因此可的其它邊都不可能在回路中，因此可刪去第刪去第6行行；同理，進(jìn)入到頂點(diǎn)同理，進(jìn)入到頂點(diǎn)3的其它邊都不可能在回路中，的其它邊都不可能在回路中，因此又可因此又可刪去第刪去第3列列。此時(shí)，邊。此時(shí)，邊(3, 6)不可能出現(xiàn)在不可能出現(xiàn)在回路中，令邊回路中，令邊(3, 6)的權(quán)值為的權(quán)值為，矩陣化為：，矩陣化為：0021304983320121291217300630206 5 4 2 15432161繼續(xù)依次計(jì)算，并實(shí)施分繼續(xù)依次計(jì)算，并實(shí)施分支和定界，具體過(guò)程如圖支和定界，具體過(guò)程如圖73所示：所示：圖圖73 降階分支定界過(guò)程降階分支定界過(guò)程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), 回路總長(zhǎng)104，由此可將下界b大于104的分支剪去。62e63 = 1，e46 = 0下的縮減矩陣：下的縮減矩陣： 00213175100121291217300630206 5 4 2 15432163e63 = e46 = 1下的縮減矩陣：下的縮減矩陣：0213012917300302053215 4 2 164e63 = e46 = 1，e21 = 0下的縮減矩陣：下的縮減矩陣：02100126013302053215 4 2 165e63 = e46 = e21 = 1下的縮減矩陣：下的縮減矩陣：020002805315 4 266e63 = e46 = e21 = 1，e14 = 0下的縮減矩陣：下的縮減矩陣：0200005315 4 267e63 = e46 = e21 = e14 = 1下的縮減矩陣：下的縮減矩陣：2000535 268e63 = e46 = 1，e21 = e51 = 0下的縮減矩陣：下的縮減矩陣：021010013302053215 4 2 169e63 = e46 = e51 =1，e21 = 0下的縮減矩陣：下的縮減矩陣：01011003215 4 270e63 = e46 = e51 = 1，e21 = e14 = 0下的縮減矩陣：下的縮減矩陣：010003215 4 271e63 = e46 = e51 = e14 = 1，e21 = 0下的縮減矩陣：下的縮減矩陣：000325 272 最后可得到兩個(gè)最優(yōu)最后可得到兩個(gè)最優(yōu)TSP回路：回路：(1, 4, 6, 3, 2, 5, 1) 和和 (1, 4, 6, 3, 5, 2, 1)，最優(yōu)回路長(zhǎng)度為，最優(yōu)回路長(zhǎng)度為104。 若將無(wú)向圖中的每條邊看成有向圖中方向相反若將無(wú)向圖中的每條邊看成有向圖中方向相反的兩條邊，則無(wú)向圖也可看成是有向圖，因此，基的兩條邊，則無(wú)向圖也可看成是有向圖，因此，基于降階的分支定界法也可用來(lái)求解無(wú)向于降階的分支定界法也可用來(lái)求解無(wú)向TSP問(wèn)題。問(wèn)題。73三、動(dòng)態(tài)規(guī)劃法定理定理1 TSP滿足滿足最優(yōu)性原理最優(yōu)性原理。可以表述為：可以表述為：“一個(gè)過(guò)程的最優(yōu)策一個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)略具有這樣的性質(zhì),即無(wú)論初始狀態(tài)和初始決策如何即無(wú)論初始狀態(tài)和初始決策如何,對(duì)于先前決策所形成的狀態(tài)而言對(duì)于先前決策所形成的狀態(tài)而言,其以后的所有決策其以后的所有決策必構(gòu)成最優(yōu)策略，必構(gòu)成最優(yōu)策略，”74證：證： 設(shè)設(shè)s, s1, s2, , sp, s是從是從s出發(fā)的一條總長(zhǎng)最短的簡(jiǎn)出發(fā)的一條總長(zhǎng)最短的簡(jiǎn)單回路，假設(shè)從單回路，假設(shè)從s到下一個(gè)城市到下一個(gè)城市s1已經(jīng)求出，則問(wèn)題已經(jīng)求出，則問(wèn)題轉(zhuǎn)化為求從轉(zhuǎn)化為求從s1到到s的最短路徑，顯然的最短路徑，顯然s1, s2, , sp, s一一定構(gòu)成一條從定構(gòu)成一條從s1到到s的最短路徑。若不然，設(shè)的最短路徑。若不然，設(shè)s1, r1, r2, , rq, s是一條從是一條從s1到到s的最短路徑且經(jīng)過(guò)的最短路徑且經(jīng)過(guò)n-1個(gè)不個(gè)不同城市，則同城市，則s, s1, r1, r2, , rq, s將是一條從將是一條從s出發(fā)的路出發(fā)的路徑長(zhǎng)度最短的簡(jiǎn)單回路且比徑長(zhǎng)度最短的簡(jiǎn)單回路且比s, s1, s2, , sp, s要短，要短，從而導(dǎo)致矛盾。所以，從而導(dǎo)致矛盾。所以，TSP滿足最優(yōu)性原理。滿足最優(yōu)性原理。75 設(shè)設(shè)TSP頂點(diǎn)編號(hào)分別為頂點(diǎn)編號(hào)分別為0，1，2，n，假設(shè)，假設(shè)從頂點(diǎn)從頂點(diǎn)0出發(fā)，令出發(fā)，令d (i, V )表示從頂點(diǎn)表示從頂點(diǎn) i 出發(fā)經(jīng)過(guò)出發(fā)經(jīng)過(guò)V 中各頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)中各頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)0的最短的最短路徑長(zhǎng)度，中間計(jì)算過(guò)程中的路徑長(zhǎng)度，中間計(jì)算過(guò)程中的d (k, Vk)也表示也表示從頂點(diǎn)從頂點(diǎn) k 出發(fā)經(jīng)過(guò)出發(fā)經(jīng)過(guò)Vk 中各頂點(diǎn)一次且僅一次，中各頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)最后回到出發(fā)點(diǎn)0（注意不是（注意不是k）的最短路徑長(zhǎng)度。）的最短路徑長(zhǎng)度。開(kāi)始時(shí)，開(kāi)始時(shí)，V = Vi，cij為頂點(diǎn)為頂點(diǎn) i 至頂點(diǎn)至頂點(diǎn) j 的距離，的距離，于是，于是，TSP的動(dòng)態(tài)規(guī)劃遞推函數(shù)可寫(xiě)成：的動(dòng)態(tài)規(guī)劃遞推函數(shù)可寫(xiě)成：76d (i, V ) = min cik + d (k, Vk) ( kV )d (k, ) = ck 0 ( k 0 )例例3 求解有向求解有向TSP：367523642375C77解：解： 從城市從城市0出發(fā)經(jīng)城市出發(fā)經(jīng)城市1、2、3然后回到城市然后回到城市0的最的最短路徑長(zhǎng)度為：短路徑長(zhǎng)度為：d (0, 1, 2, 3) = min c01 + d (1, 2,3), c02 + d (2, 1,3), c03 + d (3, 1, 2)這是最后一個(gè)階段的決策，而這是最后一個(gè)階段的決策，而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)；這一階段的決策又依賴于下述計(jì)算結(jié)果：這一階段的決策又依賴于下述計(jì)算結(jié)果：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, )；而下式可以直接獲得（括號(hào)中是該決策引起的狀態(tài)轉(zhuǎn)而下式可以直接獲得（括號(hào)中是該決策引起的狀態(tài)轉(zhuǎn)移）：移）：d (1, ) = c10 = 5 (10)，d (2, ) = c20 = 6 (20)，d (3, ) = c30 = 3 (30)； 79再向前倒推，有：再向前倒推，有：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 (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)；80再向前倒推，有：再向前倒推，有：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)，d (3, 1, 2) = min c31 + d (1, 2), c32 + d (2, 1) = min 7+8, 5+9 = 14 (32)； 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 (01)。即，從頂點(diǎn)即，從頂點(diǎn)0出發(fā)的出發(fā)的TSP最短回路長(zhǎng)度為最短回路長(zhǎng)度為10，回路路徑，回路路徑為：為：01230。82四、近似算法 由于精確式算法所能求解的問(wèn)題規(guī)模非常有限，由于精確式算法所能求解的問(wèn)題規(guī)模非常有限，實(shí)際中真正使用的往往都是多項(xiàng)式階數(shù)的近似算法實(shí)際中真正使用的往往都是多項(xiàng)式階數(shù)的近似算法或啟發(fā)式算法，算法的好壞用或啟發(fā)式算法，算法的好壞用C/C*來(lái)衡量，其中，來(lái)衡量，其中，C為近似算法所得的總行程，為近似算法所得的總行程，C*為最優(yōu)總行程，為最優(yōu)總行程，為為最最“壞壞“情況下近似與最優(yōu)總行程之比所不超過(guò)的情況下近似與最優(yōu)總行程之比所不超過(guò)的上界值。這里，列舉幾個(gè)常見(jiàn)的上界值。這里，列舉幾個(gè)常見(jiàn)的TSP快速近似算法。快速近似算法。83 旅行售貨員問(wèn)題的一些特殊性質(zhì)特殊性質(zhì)： 比如，費(fèi)用函數(shù)w往往具有三角不等式性質(zhì)三角不等式性質(zhì)，即對(duì)任意的3個(gè)頂點(diǎn)u,v,wV，有：w(u,w)w(u,v)+w(v,w)。當(dāng)圖G中的頂點(diǎn)就是平面上的點(diǎn)，任意2頂點(diǎn)間的費(fèi)用就是這2點(diǎn)間的歐氏距離時(shí)，費(fèi)用函數(shù)w就具有三角不等式性質(zhì)。 對(duì)于給定的無(wú)向圖G，可以利用找圖圖G的最小的最小生成樹(shù)生成樹(shù)的算法設(shè)計(jì)找近似最優(yōu)的旅行售貨員回路的算法。 84 當(dāng)費(fèi)用函數(shù)滿足三角不等式時(shí)，算法當(dāng)費(fèi)用函數(shù)滿足三角不等式時(shí)，算法找出的旅行售貨員回路的費(fèi)用不會(huì)超過(guò)最找出的旅行售貨員回路的費(fèi)用不會(huì)超過(guò)最優(yōu)旅行售貨員回路費(fèi)用的優(yōu)旅行售貨員回路費(fèi)用的2倍。倍。 void approxTSP (Graph g) (1)選擇g的任一頂點(diǎn)r； (2)用Prim算法找出帶權(quán)圖g的一棵以r為根的最小生成樹(shù)T； (3)前序遍歷樹(shù)T得到的頂點(diǎn)表L； (4)將r加到表L的末尾，按表L中頂點(diǎn)次序組成回路H，作為計(jì)算結(jié)果返回； 85(b)表示找到的最小生成樹(shù)表示找到的最小生成樹(shù)T；(c)表示對(duì)表示對(duì)T作前序遍歷的次序；作前序遍歷的次序；(d)表示表示L產(chǎn)生的哈密頓回路產(chǎn)生的哈密頓回路H；(e)是是G的一個(gè)最小費(fèi)用旅行售貨的一個(gè)最小費(fèi)用旅行售貨員回路。員回路。 為什么：為什么：當(dāng)費(fèi)用函數(shù)滿足三角不等式時(shí)，當(dāng)費(fèi)用函數(shù)滿足三角不等式時(shí)，算法找出的旅行售貨員回路的費(fèi)用不會(huì)超算法找出的旅行售貨員回路的費(fèi)用不會(huì)超過(guò)最優(yōu)旅行售貨員回路費(fèi)用的過(guò)最優(yōu)旅行售貨員回路費(fèi)用的2倍。倍。86答：答：存在一個(gè)最優(yōu)存在一個(gè)最優(yōu)TSP回路回路TSPOPT， TSPOPT中共有中共有n條邊，現(xiàn)條邊，現(xiàn)去掉去掉TOPT中最長(zhǎng)的一條邊，得路徑中最長(zhǎng)的一條邊，得路徑POPT， POPT中共有中共有n-1條條邊，其總權(quán)值之和邊，其總權(quán)值之和WTSP大于等于最小生成樹(shù)的總權(quán)值之和大于等于最小生成樹(shù)的總權(quán)值之和WT；即；即WTSP WT,下面只需證明該算法求得的下面只需證明該算法求得的TSP回路總長(zhǎng)回路總長(zhǎng)度之和度之和WA小于等于小于等于2WT即可；即可； 把最小生成樹(shù)中的邊重復(fù)一次，再根據(jù)三角不等式就可把最小生成樹(shù)中的邊重復(fù)一次，再根據(jù)三角不等式就可得出結(jié)論（多次利用三角不等式）。得出結(jié)論（多次利用三角不等式）。 為什么：為什么：當(dāng)費(fèi)用函數(shù)滿足三角不等式時(shí)，當(dāng)費(fèi)用函數(shù)滿足三角不等式時(shí)，算法找出的旅行售貨員回路的費(fèi)用不會(huì)超算法找出的旅行售貨員回路的費(fèi)用不會(huì)超過(guò)最優(yōu)旅行售貨員回路費(fèi)用的過(guò)最優(yōu)旅行售貨員回路費(fèi)用的2倍。倍。87 把最小生成樹(shù)中的邊重復(fù)一次，再根據(jù)三角不等式就可把最小生成樹(shù)中的邊重復(fù)一次，再根據(jù)三角不等式就可得出結(jié)論（多次利用三角不等式）。（得出結(jié)論（多次利用三角不等式）。（d）中藍(lán)色的邊為原）中藍(lán)色的邊為原來(lái)不在最小生成樹(shù)中的邊，最小生成樹(shù)中的邊重復(fù)一次及不來(lái)不在最小生成樹(shù)中的邊，最小生成樹(shù)中的邊重復(fù)一次及不在在(d)中，但在中，但在(b)中的邊反復(fù)利用三角不等式就可得出結(jié)論。中的邊反復(fù)利用三角不等式就可得出結(jié)論。881. 插入算法插入算法插入型算法可按插入規(guī)則的不同而分為若干類，其一般思想為：插入型算法可按插入規(guī)則的不同而分為若干類，其一般思想為：Step 1. 通過(guò)某種插入方式選擇插入邊通過(guò)某種插入方式選擇插入邊( i, j ) 和插入點(diǎn)和插入點(diǎn) k，將，將 k 插入插入 i 和和 j 之間之間, 形成形成, i, k , j ,。Step 2. 依次進(jìn)行，直至形成回路解。依次進(jìn)行，直至形成回路解。適用范圍：對(duì)稱型適用范圍：對(duì)稱型TSP。具體實(shí)施中，可將出發(fā)點(diǎn)取遍具體實(shí)施中，可將出發(fā)點(diǎn)取遍V中各點(diǎn)而得到多個(gè)解，并從中中各點(diǎn)而得到多個(gè)解，并從中選擇最好的一個(gè)，但此時(shí)的時(shí)間復(fù)雜度增加了選擇最好的一個(gè)，但此時(shí)的時(shí)間復(fù)雜度增加了n倍。倍。 主要的插入型算法有：主要的插入型算法有：89(1) 最近插入法最近插入法最壞情況：最壞情況：= 2； 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O (n2)。(2) 最小插入法最小插入法最壞情況：最壞情況：= 2； 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O (n2 lg n) 。(3) 任意插入法任意插入法最壞情況：最壞情況：= 2 1g n + 0.16； 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O (n2)。(4) 最遠(yuǎn)插入法最遠(yuǎn)插入法最壞情況：最壞情況：= 2 1g n + 0.16； 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O (n2)。(5) 凸核插入法凸核插入法最壞情況：最壞情況：= 未知；未知； 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O (n2lg n)。90插入法插入法(Insertion Method)1 任選一節(jié)點(diǎn)為起點(diǎn)任選一節(jié)點(diǎn)為起點(diǎn)a；2 尋找距離節(jié)點(diǎn)尋找距離節(jié)點(diǎn)a最近的節(jié)點(diǎn)最近的節(jié)點(diǎn)b作為下一個(gè)造訪的節(jié)點(diǎn)，作為下一個(gè)造訪的節(jié)點(diǎn)，形成形成a-b-a的子回路；的子回路；3 尋找距離子回路最近的節(jié)點(diǎn)尋找距離子回路最近的節(jié)點(diǎn)k作為下一個(gè)插入點(diǎn)；作為下一個(gè)插入點(diǎn)；4 尋找插入成本最小的位置尋找插入成本最小的位置(i-j)，將，將k插入插入i-j之間，形之間，形成新的子回路；成新的子回路； 插入成本：插入成本：Cik+Ckj-Cij5 重復(fù)步驟重復(fù)步驟34，直到所有節(jié)點(diǎn)均已插入回路之中，直到所有節(jié)點(diǎn)均已插入回路之中，即形成一個(gè)即形成一個(gè)TSP的可行解。的可行解。91插入法插入法14235743875534814141333373337317224525727421455885845455582145541 任選一節(jié)點(diǎn)為起點(diǎn)任選一節(jié)點(diǎn)為起點(diǎn)a；2 尋