旅行售貨員問題

——計算復雜性理論介紹2023/5/241問題的描述

售貨員要到若干城市去推銷商品，已知各城市之間的路程(或旅費)。他要選定一條從駐地出發(fā)，經過每個城市一次，最后回到駐地的路線，使總的路程(或總旅費)最小。

旅行售貨員問題雖然易于被人理解，但其計算復雜度卻是問題的輸入規(guī)模的指數(shù)函數(shù),是一個NP完全問題。2023/5/242問題的描述路線是一個帶權圖。圖中各邊的費用（權）為正數(shù)。圖的一條周游路線是包括V中的每個頂點在內的一條回路。周游路線的費用是這條路線上所有邊的費用之和。用圖論的術語來描述旅行售貨員問題：即在一個正權完全圖中尋找一個具有最小權的哈密頓回路，對于此問題，由于完全圖中必然存在哈密頓回路，目前可以用于求解的方法有枚舉法，分枝限界法，這兩種算法可以求得此問題的精確解，但到目前為止，還沒有求解這一問題的有效算法，我們可以利用分支限界法，回溯法求解此問題的近似解，以求得與最優(yōu)解最為接近的解。2023/5/243旅行售貨員問題枚舉法復雜度極高，可以求出精確解通過對問題的排列樹的合理剪枝，大大縮減了問題需要求解的時間?？梢郧蟪鼍_解基于三角不等式性質等，進一步抽象求解過程，可以求出近似解，復雜度為多項式級別問題的精確解和近似解分支限界法NP問題近似算法回溯法

通過對排列樹的剪枝，縮減問題需要的求解時間。可求精確解及近似解2023/5/244共有6條周游路線：（1,2,4,3,1）66（1,2,3,4,1）59（1,3,2,4,1）25（1,3,4,2,1）66（1,4,2,3,1）25（1,4,3,2,1）59設G=(V,E)是一個帶權圖。圖中各邊的權值為正數(shù)。圖的一條周游路線是包括V中的每個頂點在內的一條回路。旅行售貨員問題的解空間可以組織成一棵樹，從樹的根結點到任一葉結點的路徑定義了圖G的一條周游路線。周游路線的費用是這條路線上所有邊的費用之和。旅行售貨員問題要找出費用最小的周游路線。實例：4個城市n=4葉節(jié)點個數(shù)(周游線路)=(n-1)!枚舉法6659256625592023/5/245從第一個城市到第二個城市有n-1種走法，從第二個城市到第三個城市有n-2種走法……因而共有(n-1)!種走法。若考慮v1v2…vnv1和v1

vn

vn-1…v2

v1是同一條回路，還共有(1/2)(n-1)!條不同的哈密頓回路。為了比較權的大小，對每條哈密頓回路要做n-1次加法，故加法的總數(shù)為(1/2)(n-1)(n-1)!。時間復雜度O(n!)

例如當有40個城市時，(1/2)(n-1)(n-1)!的近似值為3.77×10^47，假設一臺計算機每秒完成1011次（百億）次加法，將需要超過1.19×1029年才能完成所需的加法次數(shù)，顯然是不可能的。算法效率2023/5/2461、有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法。

2、回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當大的問題。

3、回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含（剪枝過程），則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。生成問題狀態(tài)的基本方法擴展結點:一個正在產生兒子的結點

活結點:一個自身已生成但其兒子還沒有全部生成的結點

死結點:一個所有兒子已經產生的結點深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結點R，一旦產生了它的一個兒子C，就把C當做新的擴展結點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結點，繼續(xù)生成R的下一個兒子（如果存在）回溯法2023/5/247基本思想一.解空間樹的動態(tài)搜索回溯法從根結點出發(fā)，按照深度優(yōu)先策略遍歷解空間樹，搜索滿足約束條件的解。初始時，根結點成為一個活結點，同時也稱為當前的擴展結點。在當前擴展結點處，搜索向縱深方向移至一個新結點。這個新結點成為一個新的活結點，并成為當前的擴展結點。如果在當前的擴展結點處不能再向深方向移動，則當前的擴展結點就成為一個死結點。此時，應往回移動回溯至最近的一個活結點處，并使這個活結點成為當前的擴展結點。回溯法以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已無活結點時為止。2023/5/248二.常用剪枝函數(shù)：用約束函數(shù)在擴展結點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。為了避免生成那些不可能產生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死(剪枝)那些實際上不可能產生所需解的活結點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法?；厮莘?窮舉+剪枝2023/5/249解空間樹的動態(tài)搜索將圖中n個頂點編號為1,2,…,n，以頂點1為起點，旅行回路描述為1,x1,x2,..,xn,1，其中x1,x2,..,xn為頂點2,3,4,…,n的1個排列，因此解空間大小為(n-1)!ABDHN2023/5/2410剪枝2023/5/2411算法描述旅行售貨員問題的解空間是一棵排列樹。開始時，x=[1,2,…,n]相應的排列樹由x=[1:n]的所有排列構成。在遞歸算法Backtrack中，1.當i=n時，當前擴展節(jié)點是排列樹的葉節(jié)點的父節(jié)點。①檢測圖G是否存在一條從頂點x[n-1]到頂點x[n]的邊和一條從頂點x[n]到頂點1的邊。②如果這兩條邊都存在，則找到一條旅行員售貨回路。③此時，算法還需要判斷這條回路的費用是否優(yōu)于已找到的當前最優(yōu)回流的費用bestc。④如果是，則必須更新當前最優(yōu)值bestc和當前最優(yōu)解bestx。2.當i<n時，當前擴展節(jié)點位于排列樹的第i-1層。①圖G中存在從頂點x[i-1]到頂點x[i]的邊時，x[1:i]構成圖G的一條路徑，且當x[1:i]的費用小于當前最優(yōu)值時算法進入樹的第i層，②否則將剪去相應的子樹。

2023/5/2412privatestaticvoidbacktrack(inti){ if(i==n){//當前擴展結點是排列樹的葉結點的父結點 if(a[x[n-1]][x[n]]<max_value&&//頂點n-1和n之間有邊a[x[n]][1]<max_value||

//頂點n到1之間有邊cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc)){for(intj=1;j<=n;j++)bestx[j]=x[j];//得到最優(yōu)解bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];//得到最優(yōu)值}}else{//i<n,當前擴展結點位于第i-1層

cc:記錄當前路徑x[1:i]的費用a[][]:圖G的鄰接矩陣2023/5/2413for(intj=i;j<=n;j++)//搜索第i層的所有子樹

//是否可進入x[j]子樹？if(a[x[i-1]][x[j]]<max_value&&(bestc==max_value||cc+a[x[i-1]][x[j]]<bestc))

{//搜索子樹swap(x,i,j);//交換x[i],x[j]的值cc+=a[x[i-1]][x[i]];backtrack(i+1);//進入下一層子樹cc-=a[x[i-1]][x[i]];//還原cc的值swap(x,i,j);//還原x[i],x[j]的值}}}2023/5/2414Backtrack最壞情況下時間復雜度O((n-1)!)更新bestx時間復雜度O(n)

時間復雜度很高O(n!)

算法效率2023/5/24151.分支限界法基本思想

分支限界法常以廣度優(yōu)先或以最小耗費(最大效益)優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結點只有一次機會成為擴展結點。①活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優(yōu)解的兒子結點被舍棄，其余兒子結點被加入活結點表中。②此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續(xù)到找到所需的解或活結點表為空時為止。

2.常見的兩種分支限界法從活結點表中選擇下一擴展結點的不同方式導致不同的（1）隊列式(FIFO)分支限界法將活結點表組織成一個隊列，并按隊列的先進先出原則選取下一個結點為當前擴展結點（2）優(yōu)先隊列式分支限界法將活結點表組織成一個優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結點優(yōu)先級選取優(yōu)先級最高的下一個結點為當前擴展結點

最大優(yōu)先隊列：使用最大堆，體現(xiàn)最大效益優(yōu)先

最小優(yōu)先隊列：使用最小堆，體現(xiàn)最小費用優(yōu)先分支限界法2023/5/24161.求解目標回溯法：找出解空間中滿足約束條件的所有解分支限界法找出滿足約束條件的一個解在滿足約束條件的解中找出使某一目標函數(shù)值極大或極小的解分支限界法和回溯法一樣都是在解空間上搜索問題解的算法2.搜索方式深度優(yōu)先DFS回溯法：分支限界法廣度優(yōu)先BFS或最小損耗優(yōu)先2023/5/2417C=301142662514592524算法描述：①

準備工作：建立小根堆，用于存儲活動節(jié)點。計算每個頂點的最小出邊，若存在某個頂點沒有出邊，則算法終止。初始化樹根（頂點1）為第一個活動節(jié)點。

②判斷節(jié)點是否是葉結點的父節(jié)點：是的話，則檢查是否一定有最低耗費，若是加入小根堆；

③不是葉結點的父節(jié)點，則生成子節(jié)點，并判斷子節(jié)點是否有可能取得最低耗費，若可能則加入小根堆；

④取出下一個節(jié)點作為活動節(jié)點，若該節(jié)點已經是葉結點，返回當前最低耗費值，即為最優(yōu)旅行。若不是葉結點則循環(huán)2、3步。鄰接矩陣2023/5/2418優(yōu)先隊列式分支限界法用極小堆存儲活結點表E46DC30B被擴展后，它的三個兒子結點C,D,E被依次插入堆中D6C30D6C30JK1424E被擴展后，它的兒子結點J,K被依次插入當前堆中J14C30K24HJ1430K2411I26CKH1130J1424I26CD被擴展后，它的兒子結點H,I被依次插入當前堆中初始擴展結點為B，優(yōu)先隊列為空。2023/5/2419{}；B{E,D,C}；E{D,J,K,C}；D{H,J,K,I,C}；H{J,K,I,C}；J{K,I,C}；K{I,C}；I{C}；C{}.K被擴展后，得到可行解費用為59，高于當前最優(yōu)解25H被擴展后，得到一條旅行售貨員回路（1,3,2,4,1），相應的費用為25結點I本身的費用已高于當前最優(yōu)解，故沒必要擴展結點IIJ1430K2426CJ被擴展后，得到另一條費用為25的回路（1,4,2,3,1）K2426IC30I26C30C300結點C本身的費用也已高于當前最優(yōu)解，故沒必要擴展結點C此時，優(yōu)先隊列為空，算法終止。2023/5/2420NP問題近似算法從實際應用中抽象出的旅行售貨員問題具有一些特殊性質。比如，費用函數(shù)c往往具有三角不等式性質，即對任意3個頂點u,v,w有c(u,v)<=c(u,v)+c(v,w)。當圖G的頂點是平面上的點，且任意兩頂點間的費用是這兩點間的歐氏距離時，費用函數(shù)c具有三角不等式性質?？梢宰C明，即使費用函數(shù)具有三角不等式性質,旅行售貨員問題仍為NP完全問題。所以設計一個近似算法。當費用函數(shù)滿足三角不等式時，該算法不會超過最優(yōu)旅行售貨員回路費用的2倍。在費用函數(shù)不一定滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解TSP問題的多項式時間近似算法,除非P=NP。換句話說，若P≠NP，則對任意常數(shù)ρ>1，不存在性能比為ρ的解旅行售貨員問題的多項式時間近似算法。

2023/5/2421NP問題近似算法voidapproxTSP(Graghg){(1)選擇g的任意頂點r；(2)用Prim算法找出帶權圖g的一顆以r為根的最小生成樹T；(3)前序遍歷樹T得到頂點表L；(4)將r加入到表L的末尾，按表L中頂點次序組成回路H，作為計算結果返回；}2023/5/2422NP問題近似算法(a)圖G頂點集{abcdefgh)

(b)找到的最小生成樹(MST)T完全遍歷DFSabcbhbadefegeda

(c)對T作前序遍歷的順序abchdefga(d)L產生的哈密頓回路H取捷徑生成解(e)G的一個最小費用旅行售貨員回路2023/5/2423NP問題近似算法其中，a表示所給的圖G頂點集；b表示由算法找到的一顆最小生成樹T；c表示對樹T所做的前序遍歷訪問各頂點的次序；d表示由T的前序遍歷頂點表示L產生的哈密頓回路H；e表示圖G的一個最小費用旅行售貨員回路。

在b時，對T的完全遍歷W={abcbhbadefegeda}，還不是一個旅行售貨員回路，它訪問了圖G中某些頂點多次。由于費用函數(shù)滿足三角不等式，可以在W的基礎上，從中刪去已訪問過的頂點，而不會增加旅行費用。若在W中刪去頂點u和w間的一個頂點v，就用邊(u,w)代替原來從u到w的一條路。反復用這個辦法刪去W中多次訪問的頂點，可得到圖G的一條旅行售貨員回路H={abchdefga}。2023/5/2424總結(1)枚舉法

枚舉法是最差的一種算法，即將所有可能的結果都排列一次，并比較解與當前最優(yōu)解的大小，因此其時間復雜度很高O(n!)，在實際應用中當結點數(shù)很多時不可取。(2)回溯法

如果不考慮更新bestx所需的計算時間，則算法backtrack需要O