1、精選優質文檔-傾情為你奉上旅行商問題的幾種求解算法比較作者:(xxx學校)摘要:TSP問題是組合優化領域的經典問題之一,吸引了許多不同領域的研究工作者,包括數學,運籌學,物理,生物和人工智能等領域,他是目前優化領域里的熱點.本文從動態規劃法,分支界限法,回溯法分別來實現這個題目,并比較哪種更優越,來探索這個經典的NP(Nondeterministic Polynomial)難題.關鍵詞:旅行商問題 求解算法 比較一.引言旅行商問題(Travelling Salesman Problem),是計算機算法中的一個經典的難解問題,已歸為NP一完備問題類.圍繞著這個問題有各種不同的求解方法,已有的算法

2、如動態規劃法,分支限界法,回溯法等,這些精確式方法都是指數級(2n)2,3的,根本無法解決目前的實際問題,貪心法是近似方法,而啟發式算法不能保證得到的解是最優解,甚至是較好的解釋.所以我認為很多問題有快速的算法(多項式算法),但是,也有很多問題是無法用算法解決的.事實上,已經證明很多問題不可能在多項式時間內解決出來.但是,有很多很重要的問題他們的解雖然很難求解出來,表示非確定的多項式,意思是這個問題的解可以用非確定性的算法"猜"出來.如果我們有一個可以猜想的機器,我們就可以在合理的時間內找到一個比較好的解.NP-完全問題學習的簡單與否,取決于問題的難易程度.因為有很多問題,

3、它們的輸出極其復雜,比如說人們早就提出的一類被稱作NP-難題的問題.這類問題不像NP-完全問題那樣時間有限的.因為NP-問題由上述那些特征,所以很容易想到一些簡單的算法把全部的可行解算一遍.但是這種算法太慢了(通常時間復雜度為O(2n)在很多情況下是不可行的.現在,沒有知道有沒有那種精確的算法存在.證明存在或者不存在那種精確的算法這個沉重的擔子就留給了新的研究者了,或許你就是成功者.本篇論文就是想用幾種方法來就一個銷售商從幾個城市中的某一城市出發,不重復地走完其余N1個城市,并回到原出發點,在所有可能的路徑中求出路徑長度最短的一條,比較是否是最優化,哪種結果好.二.求解策略及優化算法動態規劃法

4、解TSP問題我們將具有明顯的階段劃分和狀態轉移方程的規劃稱為動態規劃,這種動態規劃是在研究多階段決策問題時推導出來的,具有嚴格的數學形式,適合用于理論上的分析.在實際應用中,許多問題的階段劃分并不明顯,這時如果刻意地劃分階段法反而麻煩.一般來說,只要該問題可以劃分成規模更小的子問題,并且原問題的最優解中包含了子問題的最優解(即滿足最優子化原理),則可以考慮用動態規劃解決.所以動態規劃的實質是分治思想和解決冗余,因此,動態規劃是一種將問題實例分解為更小的,相似的子問題,并存儲子問題的解而避免計算重復的子問題,以解決最優化問題的算法策略.旅行商問題(TSP問題)其實就是一個最優化問題,這類問題會有

5、多種可能的解,每個解都有一個值,而動態規劃找出其中最優(最大或最小)值的解.若存在若干個取最優值的解的話,它只取其中的一個.在求解過程中,該方法也是通過求解局部子問題的解達到全局最優解,但與分治法和貪心法不同的是,動態規劃允許這些子問題不獨立,(亦即各子問題可包含公共的子子問題)也允許其通過自身子問題的解作出選擇,該方法對每一個子問題只解一次,并將結果保存起來,避免每次碰到時都要重復計算.關于旅行商的問題,狀態變量是gk(i,S),表示從0出發經過k個城市到達i的最短距離,S為包含k個城市的可能集合,動態規劃的遞推關系為:gk(i,S)=mingk-1(j,Sj)+dji j屬于S,dji表示

6、j-i的距離.或者我們可以用:f(S,v)表示從v出發,經過S中每個城市一次且一次,最短的路徑.f(S,v)=min f(S-u,u)+dist(v,u) u in Sf(V,1)即為所求2.分支限界法解TSP問題旅行商問題的解空間是一個排列樹,與在子集樹中進行最大收益和最小耗費分枝定界搜索類似,使用一個優先隊列,隊列中的每個元素 中都包含到達根的路徑.假設我們要尋找的是最小耗費的旅行路徑,那可以使用最小耗費分枝定界法.在實現過程中,使用一個最小優先隊列來記錄活節點,隊列中每個節點的類型為M i n H e ap N o d e.每個節點包括如下區域: x(從1到n的整數排列,其中x 0 =

7、1 ),s(一個整數,使得從排列樹的根節點到當前節點的路徑定義了旅行路徑的前綴x0:s, 而剩余待訪問的節點是x s + 1 : n - 1 ),c c(旅行路徑前綴,即解空間樹中從根節點到當前節點的耗費),l c o s t(該節點子樹中任意葉節點中的最小耗費), rc o s t(從頂點x s : n - 1 出發的所有邊的最小耗費之和).當類型為M i n He a p N o d e ( T )的數據被轉換成為類型T時,其結果即為l c o s t的值.分枝定界算法的代碼見程序.程序首先生成一個容量為1 0 0 0的最小堆,用來表示活節點的最小優先隊列.活節點按其l c o s t值從

8、最小堆中取出.接下來,計算有向圖中從每個頂點出發的邊中 耗費最小的邊所具有的耗費M i n O u t.如果某些頂點沒有出邊,則有向圖中沒有旅行 路徑,搜索終止.如果所有的頂點都有出邊,則可以啟動最小耗費分枝定界搜索.根的孩子(圖1 6 - 5的節點B)作為第一個E-節點,在此節點上,所生成的旅行路徑前綴只有一個頂點1,因此s=0, x0=1, x1:n-1是剩余的頂點(即頂點2 , 3 ,., n ).旅行路徑前綴1 的開銷為0 ,即c c = 0 ,并且,r c o st=n i=1M i n O u t .在程序中,bestc 給出了當前能找到的最少的耗費值.初始時,由于沒有找到任何旅行

9、路徑,因此b e s t c的值被設為N o E d g e.程序旅行商問題的最小耗費分枝定界算法templateT AdjacencyWDigraph:BBTSP(int v)/ 旅行商問題的最小耗費分枝定界算法/ 定義一個最多可容納1 0 0 0個活節點的最小堆MinHeap > H(1000);T *MinOut = new T n+1;/ 計算MinOut = 離開頂點i的最小耗費邊的耗費T MinSum = 0; / 離開頂點i的最小耗費邊的數目for (int i = 1; i <= n; i+) T Min = NoEdge;for (int j = 1; j <

10、;= n; j+)if (aj != NoEdge &&(aj < Min | Min = NoEdge)Min = aj;if (Min = NoEdge) return NoEdge; / 此路不通MinOut = Min;MinSum += Min;/ 把E-節點初始化為樹根MinHeapNode E;E.x = new int n;for (i = 0; i < n; i+)E.x = i + 1;E.s = 0; / 局部旅行路徑為x 1 : 0 E.cc = 0; / 其耗費為0E.rcost = MinSum;T bestc = NoEdge; / 目

11、前沒有找到旅行路徑/ 搜索排列樹while (E.s < n - 1) / 不是葉子if (E.s = n - 2) / 葉子的父節點/ 通過添加兩條邊來完成旅行/ 檢查新的旅行路徑是不是更好if (aE.xn-2E.xn-1 != NoEdge && aE.xn-11 != NoEdge && (E.cc +aE.xn-2E.xn-1 + aE.xn-11 < bestc | bestc = NoEdge) / 找到更優的旅行路徑bestc = E.cc + aE.xn-2E.xn-1 + aE.xn-11;E.cc = bestc;E.lcost

12、 = bestc;E . s + + ;H . I n s e r t ( E ) ; else delete E.x;else / 產生孩子for (int i = E.s + 1; i < n; i+)if (aE.xE.sE.x != NoEdge) / 可行的孩子, 限定了路徑的耗費T cc = E.cc + aE.xE.sE.x;T rcost = E.rcost - MinOutE.xE.s;T b = cc + rcost; /下限if (b < bestc | bestc = NoEdge) / 子樹可能有更好的葉子/ 把根保存到最大堆中MinHeapNode N;

13、N.x = new int n;for (int j = 0; j < n; j+)N.xj = E.xj;N.xE.s+1 = E.x;N.x = E.xE.s+1;N.cc = cc;N.s = E.s + 1;N.lcost = b;N.rcost = rcost;H . I n s e r t ( N ) ; / 結束可行的孩子delete E.x; / 對本節點的處理結束try H.DeleteMin(E); / 取下一個E-節點catch (OutOfBounds) break; / 沒有未處理的節點if (bestc = NoEdge) return NoEdge; / 沒

14、有旅行路徑/ 將最優路徑復制到v1:n 中for (i = 0; i < n; i+)vi+1 = E.x;while (true) /釋放最小堆中的所有節點delete E.x;try H.DeleteMin(E);catch (OutOfBounds) break;return bestc;while 循環不斷地展開E-節點,直到找到一個葉節點.當s = n - 1時即可說明找到了 一個葉節點.旅行路徑前綴是x 0 : n - 1 ,這個前綴中包含了有向圖中所有的n個頂點.因此s = n - 1的活節點即為一個葉節點.由于算法本身的性質,在葉節點上lco st 和cc 恰好等于葉節點

15、對應的旅行路徑的耗費.由于所有剩余的活節點的lcost 值都大于等于從最小堆中取出的第一個葉節點的lcost 值,所以它們并不能幫助我們找到更好的葉節點,因此,當某個葉節點成為E-節點后,搜索過程即終止.while 循環體被分別按兩種情況處理,一種是處理s = n - 2的E-節點,這時,E-節點是某個單獨葉節點的父節點.如果這個葉節點對應的是一個可行的旅行路徑,并且此旅行路徑的耗費小于當前所能找到的最小耗費,則此葉節點被插入最小堆中,否則葉節點被刪除,并開始處理下一個E-節點.其余的E-節點都放在while 循環的第二種情況中處理.首先,為每個E-節點生成它的兩個子節點,由于每個E-節點代表

16、著一條可行的路徑x 0 : s ,因此當且僅當 是有向圖的邊且x i 是路徑x s + 1 : n - 1 上的頂點時,它的子節點可行.對于每個可行的孩子節點,將邊 的耗費加上E.cc 即可得到此孩子節點的路徑前綴( x 0 : s ,x) 的耗費c c.由于每個包含此前綴的旅行路徑都必須包含離開每個剩余頂點的出邊,因此任何葉節點對應的耗費都不可能小于cc 加上離開各剩余頂點的出邊耗費的最小值之和,因而可以把這個下限值作為E-節點所生成孩子的lcost 值.如果新生成孩子的lcost 值小于目前找到的最優旅行路徑的耗費b e s t c,則把新生成的孩子加入活節點隊列(即最小堆)中.如果有向圖

17、沒有旅行路徑,程序返回N o E d g e;否則,返回最優旅行路徑的耗費,而最優旅行路徑的頂點序列存儲在數組v 中.3.回朔法解TSP問題回朔法有"通用解題法"之稱,它采用深度優先方式系統地搜索問題的所有解,基本思路是:確定解空間的組織結構之后,從根結點出發,即第一個活結點和第一個擴展結點向縱深方向轉移至一個新結點,這個結點成為新的活結點,并成為當前擴展結點.如果在當前擴展結點處不能再向縱深方向轉移,則當前擴展結點成為死結點.此時,回溯到最近的活結點處,并使其成為當前擴展結點,回溯到以這種工作方式遞歸地在解空間中搜索,直到找到所求解空間中已經無活結點為止.旅行商問題的解空

18、間是一棵排列樹.對于排列樹的回溯搜索與生成1,2, n的所有排列的遞歸算法Perm類似.設開始時x= 1,2, n ,則相應的排列樹由x 1:n 的所有排列構成.旅行商問題的回溯算法找旅行商回路的回溯算法Backtrack是類Treveling的私有成員函數,TSP是Treveling的友員.TSP(v)返回旅行售貨員回路最小費用.整型數組v返回相應的回路.如果所給的圖G不含旅行售貨員回路,則返回NoEdge.函數TSP所作的工作主要是為調用Backtrack所需要變量初始化.由TSP調用Backtrack(2)搜索整個解空間.在遞歸函數Backtrack中,當i = n時,當前擴展結點是排列

19、樹的葉結點的父結點.此時,算法檢測圖G是否存在一條從頂點x n-1 到頂點x n 的邊和一條從頂點x n 到頂點1的邊.如果這兩條邊都存在,則找一條旅行售貨員回路.此時,算法還需判斷這條回路的費用是否優于已找到的當前最優回路的費用best.如果是,則必須更新當前最優值bestc和當前最優解bestx.當i < n時,當前擴展結點位于排列樹的第i1 層.圖G中存在從頂點x i-1 到頂點x i 的邊時,x 1:i 構成圖G的一條路徑,且當x 1:i 的費用小于當前最優值時,算法進入排列樹的第I層.否則將剪去相應的子樹.算法中用變量cc記錄當前路徑x 1:i 的費用.解旅行商售貨員問題的回溯

20、法可描述如下:templateclass Traveling friend Type TSP(int * *,int ,Type);private:void Backtrack(int i);int n, /圖G的頂點數* x, /當前解*bestx; /當前最優解Type * *a, /圖G的鄰接矩陣cc, /當前費用bestc, /當前最優值NoEdge; /無邊際記;templatevode Traveling:Backtrack(int i)if(I=n)if(axn-1xn! = NoEdge &&axn1!= NoEdge &&(cc + axn-1

21、xn+axn1bestc= NoEdge) )for(int j=1;j<=n;j+)bestxj=xj;bestc =cc + axn-1xn+ axn1;else for(int j=I; j<=n;j+)/是否可進入xj子樹if(axi-1xj! = NoEdge &&(cc + axi-1xi< bestc|bestc = NoEdge/搜索子數Swap(xi,xj);cc += axi-1xi;Backtrack(I+1);cc -= axi-1xi;Swap(xi,xj);templateType TSP(Type * *a,int v,int n

22、,Type NoEdge)Traveling Y;/初始化YY.x = new intn+1;/ 置x為單位排列for(int i=1;i<=n;i+)Y.xi = I;Y.a=a;Y.n=n;Y.bestc = NoEdge;Y.bestc = v;Y.cc = 0;Y. NoEdge = NoEdge;/搜索x2:n的全排列Y.Backtrack(2);Delete Y.x;三.三種方法的比較1.動態規劃法和回朔法的比較:這本來就是兩個完全不同的領域,一個是算法領域,一個是數據結構問題.但兩者又交叉,又有區別.從本質上講就是算法與數據結構的本質區別,回朔是一個具體的算法,動態規劃是數

23、據結構中的一個概念.動態規劃講究的是狀態的轉化,以狀態為基準,確定算法,動態規劃法所針對的問題有一個顯著的特征,即它所對應的子問題樹中的子問題呈現大量的重復.動態規劃法的關鍵就在于,對于重復出現的子問題,只在第一次遇到時加以求解,并把答案保存起來,讓以后再遇到時直接引用,不必重新求解.簡單的說就是:動態規劃法是從小單元開始積累計算結果.回朔講究過程的推進與反還,隨數據的搜索,標記,確定下一步的行進方向,回朔是去搜索.如果想要搜索時,發現有很多重復計算,就應該想到用動態規劃了.動態規劃和搜索都可以解決具有最優子結構的問題,然而動態規劃在解決子問題的時候不重復計算已經計算過的子問題,對每個子問題只

24、計算一次;而簡單的搜索則遞歸地計算所有遇到的的子問題.比如一個問題的搜索樹具有如下形式:.A./.B.C././.D.E.F如果使用一般深度優先的搜索,依次搜索的順序是A-B-D-E-C-E-F,注意其中節點E被重復搜索了兩次;如果每個節點看作是一個子問題的話,節點E所代表的子問題就被重復計算了兩次;但是如果是用動態規劃,按照樹的層次劃分階段,按照自底向上的順序,則在第一階段計算D,E,F;第二階段計算B,C;第三階段計算A;這樣就沒有重復計算子問題E.搜索法的優點是實現方便,缺點是在子問題有大量的重復的時候要重復計算子問題,效率較低;動態規劃雖然效率高,但是階段的劃分和狀態的表示比較復雜,另

25、外,搜索的時候只要保存單前的結點;而動態規劃則至少要保存上一個階段的所有節點,比如在動態規劃進行到第2階段的時候,必須把第三階段的D,E,F三個節點全部保存起來,所以動態規劃是用空間換時間.另外,有一種折衷的辦法,就是備忘錄法,這是動態規劃的一種變形.該方法的思想是:按照一般的搜索算法解決子問題,但是用一個表將所有解決過的子問題保存起來,遇到一個子問題的時候,先查表看是否是已經解決過的,如果已解決過了就不用重復計算.比如搜索上面那棵樹,在A-B-D-E的時候,已經將E記錄在表里了,等到了A-B-D-E-C的時候,發現E已經被搜索過,就不再搜索E,而直接搜索F,因此備忘錄法的搜索順序是A-B-D

26、-E-C-(跳過E)-F自底向上的動態規劃還有一個缺點,比如對于下面的樹:.A./.B.C.G./././.D.E.F.H.I如用自底向上的動態規劃,各個階段搜索的節點依次是:D,E,F,H,IB,C,GAA才是我們最終要解決的問題,可以看到,G,H,I根本與問題A無關,但是動態規劃還是將它們也解決了一遍,這就造成了效率降低.而備忘錄法則可以避免這種問題,按照備忘錄法,搜索的次序仍然是:A-B-D-E-C-(跳過E)-F.備忘錄法的優點是實現簡單,且在子問題空間中存在大量冗余子問題的時候效率較高;但是要占用較大的內存空間(需要開一個很大的表來記錄已經解決的子問題),而且如果用遞歸實現的話遞歸壓

27、棧出棧也會影響效率;而自底向上的動態規劃一般用for循環就可以了.值得一提的是,用動態規劃法來計算旅行商的時間復雜度是指數型的.2. 分支限界法和回朔法的比較:分支限界法類似于回溯法,也是一種在問題的解空間樹T上搜索問題解的算法.但在一般情況下,分支限界與回溯法的求解目標不同.回溯法的求解目標是找出T中滿足約束條件的所有解,而分支限界法的求解目標則是找出滿足約束條件的一個解,或是在滿足約束條件的解中找出使某一目標函數值達到極大或極小的解,即在某種意義下的最優解.我們先看一個列子:設G=(V,E)是一個帶權圖.圖1中各邊的費用(權)為一正數.圖中的一條周游線是包括V中的每個頂點在內的一條回路.一

28、條周游路線的費用是這條路線上所有邊的費用之和.所謂旅行售貨員問題就是要在圖G中找出一條有最小費用的周游路線.給定一個有n個頂點的帶權圖G,旅行售貨員問題要找出圖G的費用(權)最小的周游路線.圖1是一個4頂點無向帶權圖.頂點序列1,2,4,3,1;1,3,2,4,1和1,4,3,2,1是該圖中3條不同的周游路線.301 256 1043 20 4圖1 4頂點帶權圖該問題的解空間可以組織成一棵樹,從樹的根結點到任一葉結點的路徑定義了圖G的一條周游路線.圖1是當n=4時這種樹結構的示例.其中從根結點A到葉結點L的路徑上邊的標號組成一條周游路線1,2,3,4,1.而從根結點到葉結點O的路徑則表示周游路

29、線1,3,4,2,1.圖G的每一條周游路線都恰好對應解空間樹中一條從根結點到葉結點的路徑.因此,解空間樹中葉結點個數為(n-1)!.A1B2 3 4C D E3 2 4 2 3F G H I J K4 3 4 2 3 2L M N O P Q圖2 旅行售貨員問題的解空間樹對于圖1中的圖G,用回溯法找最小費用周游路線時,從解空間樹的根結點A出發,搜索至B,C,F,L.在葉結點L處記錄找到的周游路線1,2,3,4,1,該周游路線的費用為59.從葉結點L返回至最近活動結點F處.由于F處已沒有可擴展結點,算法又返回到結點C處.結點C成為新擴展結點,由新擴展結點,算法再移至結點G 后又移至結點M,得到周

30、游路線1,2,4,3,1,其費用為66.這個費用不比已有周游路線1,2,3,4,1的費用小.因此,舍棄該結點.算法有依次返回至結點G,C,B.從結點B,算法繼續搜索至結點D,H,N.在葉結點N算法返回至結點H,D,然后再從結點D開始繼續向縱深搜索至結點O.依次方式算法繼續搜索遍整個解空間,最終得到1,3,2,4,1是一條最小費用周游路線.以上便是回溯法找最小費用周游路線的實列,但如果我們用分支限界法來解的話,會更適合.由于求解目標不同,導致分支限界法與回溯法在解空間樹T上的搜索方式也不相同.回溯法以深度優先的方式搜索解空間樹T,而分支限界法則以廣度優先或以最小消耗優先的方式搜索解空間樹T.分支

31、限界法的搜索策略是,在擴展結點處,先生成所有的兒子結點(分支),然后再從當前的活動點表中選擇下一個擴展結點.為了有效地選擇下一擴展結點,以加速搜索的進程,在每一活結點處,計算一個函數值(限界),并根據這些已計算出的函數值,從當前活結點表中選擇一個最有利的結點作為擴展結點,使搜索朝著解空間樹上的最優解的分支推進,以便盡快的找出一個最優解.四.結論:參考文獻: 動態規劃 dynamic programming圖片：圖片：圖片：圖片：圖片：圖片：圖片：圖片：圖片：圖片：圖片：圖片：圖片：dongtai guihua動態規劃(卷名：自動控制與系統工程)dynamic programming研究多段（多

32、步）決策過程最優化問題的一種數學方法，英文縮寫DP，是最優控制和運籌學的重要數學工具。為了尋找系統最優決策，可將系統運行過程劃分為若干相繼的階段（或若干步），并在每個階段（或每一步）都作出決策。這種決策過程就稱為多段（多步）決策過程。多段決策過程的每一階段的輸出狀態就是下一階段的輸入狀態。某一階段所作出的最優決策，對于下一階段未必是最有利的。多段決策過程的最優化問題必須從系統整體出發，要求各階段選定的決策序列所構成的策略最終能使目標函數達到極值。發展簡況 20世紀40年代，人們開始研究水力資源的多級分配和庫存的多級存儲問題。50年代初,美國數學家R.貝爾曼首先提出動態規劃的概念，1957年發表

33、動態規劃一書。在1961、1962年相繼出版的第二版和第三版中，又進一步闡明了動態規劃的理論和方法。多段決策過程 又稱為多步決策過程(或系統)，是一種適合采用動態規劃的過程(或系統)。多段決策過程包括階段、狀態、決策、策略和目標函數 5個要素。階段:把所要求解的過程劃分成若干相互聯系的階段,并用k表示階段變量。狀態:表示某一階段出發位置的狀態，它既是上一階段的輸出又是本階段的輸入，并用向量xk表示第k階段的狀態，稱為狀態變量。決策:指給定k階段的狀態后,從該狀態轉移到下一階段某一狀態的選擇。用Uk表示第k階段當狀態處于Xk時的決策變量。對于系統的每一個狀態，都可以從若干種可能的決策（或控制）中

34、任選一種。選定決策并加以實施，即可引起系統狀態的變化。系統的下一階段狀態由現在的狀態和決策確定，與過去的歷史無關，即系統是無記憶的。策略：由過程中每一階段所選決策構成的整個序列，又稱為方案。目標函數：策略的目標是使狀態變量的某個特定函數的值為最大（或最小）。這個特定函數就是目標函數。使目標函數值為最大（或最小）的策略稱為最優策略。圖1中求最短路徑的例子說明了多段決策過程及其構成要素。圖中S是出發點，G是目的地，各邊上的數字表示兩點間的距離。求從S到G的最短路徑和距離數。首先，可將圖1劃分成四個階段，然后逆向依次尋求使總的距離為最小的最短路徑。先從第一階段開始,從C1到G只有一條路線,同樣從C2到G也只有一條路線。到了第二階段，從B1到G有經過C1或C2兩條路線，經選擇后由B1經C2到G距離最小。如此繼續進行下去，就把一個最短路徑問題變成了多段決策問題（圖2）。最后求得最短路徑為SA2B1C2G。基本原理 動態規劃的理論基礎是最優化原理和嵌入原理。最優化原理 一個最優策略，具有如下性質：不論初始狀態和初始決策（第一步決策）如何，以第一步決策所形成的階