1、數(shù)據(jù)結(jié)構(gòu)課程常見問題 -單元30 旅行商問題1旅行商問題的幾種求解算法比較？解析：動態(tài)規(guī)劃法解TSP問題我們將具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的規(guī)劃稱為動態(tài)規(guī)劃,這種動態(tài)規(guī)劃是在研究多階段決策問題時推導(dǎo)出來的,具有嚴格的數(shù)學(xué)形式,適合用于理論上的分析.在實際應(yīng)用中,許多問題的階段劃分并不明顯,這時如果刻意地劃分階段法反而麻煩.一般來說,只要該問題可以劃分成規(guī)模更小的子問題,并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解(即滿足最優(yōu)子化原理),則可以考慮用動態(tài)規(guī)劃解決.所以動態(tài)規(guī)劃的實質(zhì)是分治思想和解決冗余,因此,動態(tài)規(guī)劃是一種將問題實例分解為更小的,相似的子問題,并存儲子問題的解而避免計算重復(fù)的子問

2、題,以解決最優(yōu)化問題的算法策略.旅行商問題(TSP問題)其實就是一個最優(yōu)化問題,這類問題會有多種可能的解,每個解都有一個值,而動態(tài)規(guī)劃找出其中最優(yōu)(最大或最小)值的解.若存在若干個取最優(yōu)值的解的話,它只取其中的一個.在求解過程中,該方法也是通過求解局部子問題的解達到全局最優(yōu)解,但與分治法和貪心法不同的是,動態(tài)規(guī)劃允許這些子問題不獨立,(亦即各子問題可包含公共的子子問題)也允許其通過自身子問題的解作出選擇,該方法對每一個子問題只解一次,并將結(jié)果保存起來,避免每次碰到時都要重復(fù)計算.關(guān)于旅行商的問題,狀態(tài)變量是gk(i,S),表示從0出發(fā)經(jīng)過k個城市到達i的最短距離,S為包含k個城市的可能集合,動

3、態(tài)規(guī)劃的遞推關(guān)系為:gk(i,S)=mingk-1(j,Sj)+dji j屬于S,dji表示j-i的距離. 或者我們可以用:f(S,v)表示從v出發(fā),經(jīng)過S中每個城市一次且一次,最短的路徑. f(S,v)=min f(S-u,u)+dist(v,u) u in S f(V,1)即為所求 2.分支限界法解TSP問題 旅行商問題的解空間是一個排列樹,與在子集樹中進行最大收益和最小耗費分枝定界搜 索類似,使用一個優(yōu)先隊列,隊列中的每個元素 中都包含到達根的路徑. 假設(shè)我們要尋找的是最小耗費的旅行路徑,那可以使用最小耗費分枝定界法.在實現(xiàn) 過程中,使用一個最小優(yōu)先隊列來記錄活節(jié)點,隊列中每個節(jié)點的類型

4、為M i n H e a p N o d e.每個節(jié)點包括如下區(qū)域: x(從1到n的整數(shù)排列,其中x 0 = 1 ),s( 一個整數(shù),使得從排列樹的根節(jié)點到當前節(jié)點的路徑定義了旅行路徑的前綴x0:s, 而 剩余待訪問的節(jié)點是x s + 1 : n - 1 ),c c(旅行路徑前綴,即解空間樹中從根 節(jié)點到當前節(jié)點的耗費),l c o s t(該節(jié)點子樹中任意葉節(jié)點中的最小耗費), r c o s t(從頂點x s : n - 1 出發(fā)的所有邊的最小耗費之和).當類型為M i n H e a p N o d e ( T )的數(shù)據(jù)被轉(zhuǎn)換成為類型T時,其結(jié)果即為l c o s t的值.分枝定界 算法

5、的代碼見程序. 程序首先生成一個容量為1 0 0 0的最小堆,用來表示活節(jié)點的最小優(yōu)先隊列.活節(jié)點按其l c o s t值從最小堆中取出.接下來,計算有向圖中從每個頂點出發(fā)的邊中 耗費最小的邊所具有的耗費M i n O u t.如果某些頂點沒有出邊,則有向圖中沒有旅行 路徑,搜索終止.如果所有的頂點都有出邊,則可以啟動最小耗費分枝定界搜索.根的孩子(圖1 6 - 5的節(jié)點B)作為第一個E-節(jié)點,在此節(jié)點上,所生成的旅行路徑前綴只有一個頂點1,因此s=0, x0=1, x1:n-1是剩余的頂點(即頂點2 , 3 ,., n ).旅行路徑前綴1 的開銷為0 ,即c c = 0 ,并且,r c o

6、st=n i=1M i n O u t .在程序中,bestc 給出了當前能找到的最少的耗費值.初始時,由于沒有找到任何旅行路徑,因此b e s t c的值被設(shè)為N o E d g e. 程序旅行商問題的最小耗費分枝定界算法 template T AdjacencyWDigraph:BBTSP(int v) / 旅行商問題的最小耗費分枝定界算法 / 定義一個最多可容納1 0 0 0個活節(jié)點的最小堆 MinHeap H(1000); T *MinOut = new T n+1; / 計算MinOut = 離開頂點i的最小耗費邊的耗費 T MinSum = 0; / 離開頂點i的最小耗費邊的數(shù)目

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

8、cc = 0; / 其耗費為0 E.rcost = MinSum; T bestc = NoEdge; / 目前沒有找到旅行路徑 / 搜索排列樹 while (E.s n - 1) / 不是葉子 if (E.s = n - 2) / 葉子的父節(jié)點 / 通過添加兩條邊來完成旅行 / 檢查新的旅行路徑是不是更好 if (aE.xn-2E.xn-1 != NoEdge & aE.xn-11 != NoEdge & (E.cc + aE.xn-2E.xn-1 + aE.xn-11 bestc | bestc = NoEdge) / 找到更優(yōu)的旅行路徑 bestc = E.cc + aE.xn-2E.x

9、n-1 + aE.xn-11; E.cc = bestc; E.lcost = bestc; E . s + + ; H . I n s e r t ( E ) ; else delete E.x; else / 產(chǎn)生孩子 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) /

10、 子樹可能有更好的葉子 / 把根保存到最大堆中 MinHeapNode N; 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 ) ; / 結(jié)束可行的孩子 delete E.x; / 對本節(jié)點的處理結(jié)束 try H.DeleteMin(E); / 取下一個E-節(jié)點 catch (OutOfBounds) break; /

11、沒有未處理的節(jié)點 if (bestc = NoEdge) return NoEdge; / 沒有旅行路徑 / 將最優(yōu)路徑復(fù)制到v1:n 中 for (i = 0; i n; i+) vi+1 = E.x; while (true) /釋放最小堆中的所有節(jié)點 delete E.x; try H.DeleteMin(E); catch (OutOfBounds) break; return bestc; while 循環(huán)不斷地展開E-節(jié)點,直到找到一個葉節(jié)點.當s = n - 1時即可說明找到了 一個葉節(jié)點.旅行路徑前綴是x 0 : n - 1 ,這個前綴中包含了有向圖中所有的n個頂點.因此s =

12、 n - 1的活節(jié)點即為一個葉節(jié)點.由于算法本身的性質(zhì),在葉節(jié)點上lco st 和cc 恰好等于葉節(jié)點對應(yīng)的旅行路徑的耗費.由于所有剩余的活節(jié)點的lcost 值都大于等于從最小堆中取出的第一個葉節(jié)點的lcost 值,所以它們并不能幫助我們找到更好的葉節(jié)點,因此,當某個葉節(jié)點成為E-節(jié)點后,搜索過程即終止.while 循環(huán)體被分別按兩種情況處理,一種是處理s = n - 2的E-節(jié)點,這時,E-節(jié)點是某個單獨葉節(jié)點的父節(jié)點.如果這個葉節(jié)點對應(yīng)的是一個可行的旅行路徑,并且此旅行路徑的耗費小于當前所能找到的最小耗費,則此葉節(jié)點被插入最小堆中,否則葉節(jié)點被刪除,并開始處理下一個E-節(jié)點. 其余的E-節(jié)

13、點都放在while 循環(huán)的第二種情況中處理.首先,為每個E-節(jié)點生成它的兩個子節(jié)點,由于每個E-節(jié)點代表著一條可行的路徑x 0 : s ,因此當且僅當 是有向圖的邊且x i 是路徑x s + 1 : n - 1 上的頂點時,它的子節(jié)點可行.對于每個可行的孩子節(jié)點,將邊 的耗費加上E.cc 即可得到此孩子節(jié)點的路徑前綴( x 0 : s ,x) 的耗費c c.由于每個包含此前綴的旅行路徑都必須包含離開每個剩余頂點的出邊,因此任何葉節(jié)點對應(yīng)的耗費都不可能小于cc 加上離開各剩余頂點的出邊耗費的最小值之和,因而可以把這個下限值作為E-節(jié)點所生成孩子的lcost 值.如果新生成孩子的lcost 值小于

14、目前找到的最優(yōu)旅行路徑的耗費b e s t c,則把新生成的孩子加入活節(jié)點隊列(即最小堆)中.如果有向圖沒有旅行路徑,程序返回N o E d g e;否則,返回最優(yōu)旅行路徑的耗費,而最優(yōu)旅行路徑的頂點序列存儲在數(shù)組v 中.3.回朔法解TSP問題回朔法有通用解題法之稱,它采用深度優(yōu)先方式系統(tǒng)地搜索問題的所有解,基本思路是:確定解空間的組織結(jié)構(gòu)之后,從根結(jié)點出發(fā),即第一個活結(jié)點和第一個擴展結(jié)點向縱深方向轉(zhuǎn)移至一個新結(jié)點,這個結(jié)點成為新的活結(jié)點,并成為當前擴展結(jié)點.如果在當前擴展結(jié)點處不能再向縱深方向轉(zhuǎn)移,則當前擴展結(jié)點成為死結(jié)點.此時,回溯到最近的活結(jié)點處,并使其成為當前擴展結(jié)點,回溯到以這種工作

15、方式遞歸地在解空間中搜索,直到找到所求解空間中已經(jīng)無活結(jié)點為止.旅行商問題的解空間是一棵排列樹.對于排列樹的回溯搜索與生成1,2, n的所有排列的遞歸算法Perm類似.設(shè)開始時x= 1,2, n ,則相應(yīng)的排列樹由x 1:n 的所有排列構(gòu)成.旅行商問題的回溯算法找旅行商回路的回溯算法Backtrack是類Treveling的私有成員函數(shù),TSP是Treveling的友員.TSP(v)返回旅行售貨員回路最小費用.整型數(shù)組v返回相應(yīng)的回路.如果所給的圖G不含旅行售貨員回路,則返回NoEdge.函數(shù)TSP所作的工作主要是為調(diào)用Backtrack所需要變量初始化.由TSP調(diào)用Backtrack(2)搜

16、索整個解空間.在遞歸函數(shù)Backtrack中,當i = n時,當前擴展結(jié)點是排列樹的葉結(jié)點的父結(jié)點.此時,算法檢測圖G是否存在一條從頂點x n-1 到頂點x n 的邊和一條從頂點x n 到頂點1的邊.如果這兩條邊都存在,則找一條旅行售貨員回路.此時,算法還需判斷這條回路的費用是否優(yōu)于已找到的當前最優(yōu)回路的費用best.如果是,則必須更新當前最優(yōu)值bestc和當前最優(yōu)解bestx.當i n時,當前擴展結(jié)點位于排列樹的第i1 層.圖G中存在從頂點x i-1 到頂點x i 的邊時,x 1:i 構(gòu)成圖G的一條路徑,且當x 1:i 的費用小于當前最優(yōu)值時,算法進入排列樹的第I層.否則將剪去相應(yīng)的子樹.算

17、法中用變量cc記錄當前路徑x 1:i 的費用.解旅行商售貨員問題的回溯法可描述如下:templateclass Traveling friend Type TSP(int * *,int ,Type);private:void Backtrack(int i);int n, /圖G的頂點數(shù) * x, /當前解*bestx; /當前最優(yōu)解Type * *a, /圖G的鄰接矩陣cc, /當前費用bestc, /當前最優(yōu)值NoEdge; /無邊際記;templatevode Traveling:Backtrack(int i)if(I=n)if(axn-1xn! = NoEdge &axn1!= NoEdge &(cc + axn-1xn+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/搜索子數(shù)Swap(xi,xj);cc +