1、數(shù)據(jù)結(jié)構(gòu)課程常見問-單元30行商問1旅行商問題的幾種求解算：TSP具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的規(guī)劃稱為動態(tài)規(guī)劃,數(shù)據(jù)結(jié)構(gòu)課程常見問-單元30行商問1旅行商問題的幾種求解算：TSP具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的規(guī)劃稱為動態(tài)規(guī)劃,時推導(dǎo)出來的,具有嚴(yán)格的數(shù)學(xué)形式,適合用于理論上的分析.在實際應(yīng)用中,許多問題的階段劃分并不明顯優(yōu)解中包含了子問題的最優(yōu)解(即滿足最優(yōu)子化原理),則可以考慮用動態(tài)規(guī)劃解決.和解決冗余,因此,動態(tài)規(guī)劃是一種將問題實例分解為更小的,相似的子問題,旅行商問題(TSP 問題)其實就是一個最優(yōu)化問題,這類問題會有多種可能的解,每個解都有一個值,方法也是通過求解局部子問題的

2、解達(dá)到全局最優(yōu)解,但與分治法和貪心法不同的是,題不獨立,(亦即各子問題可包含公共的子子問題)也允許其通過自身子問題的解作出選擇,狀態(tài)變量是gk(i,S),0出發(fā)經(jīng)過k個城市到達(dá)i的最短距離,S為包含kgk(i,S)=mingk-1(j,Sj)+djijS,djij-i的距離或f(S,v)v出發(fā),S中每個城市一次且一次,最短的路徑 uin2.TSP假活節(jié)點,MinHepNode.每個節(jié)點包括如下區(qū)域x(1n的整數(shù)排列,x01一個整數(shù),使得從排列樹的根節(jié)點到當(dāng)前節(jié)點的路徑定義了旅行路徑的前綴x0:s, 剩余的節(jié)點是xpNode.每個節(jié)點包括如下區(qū)域x(1n的整數(shù)排列,x01一個整數(shù),使得從排列樹的

3、根節(jié)點到當(dāng)前節(jié)點的路徑定義了旅行路徑的前綴x0:s, 剩余的節(jié)點是xs+1:n-1),cc(旅行路徑前綴,即解空間樹中從節(jié)點到當(dāng)前節(jié)點的耗費),lcost(該節(jié)點子樹中任意葉節(jié)點中的最小耗費cost(xsn1出發(fā)的所有邊的最小耗費之和).Minea pN odeT的數(shù)據(jù)被轉(zhuǎn)換成為類型T時,lc ost的值.1000的最小堆,用來表示活節(jié)點的最小優(yōu)先隊列.活節(jié)點按其lcost中取出.接下來,計算有向圖中從每個頂點出發(fā)的邊中 耗費最小的邊所具有的耗費MinOut.沒有出邊,則有向圖中沒有旅行 路徑,搜索終止.如果所有的頂點都有出邊,索.根的孩子(16 - 5B)E-節(jié)點,在此節(jié)點上,1,s=0,

4、x0=1, x1:n-1是剩余的頂點(2 , 3 ,., n ).1 0 ,即c c = 0 ,并且,r c st=ni=1MinOut在程序中,bestc 給出了當(dāng)前能找到的最少的耗費值.初始時,由于沒有找到任何旅行路徑be s tc 的值被設(shè)為N o Ed g T/ 旅行商問題/ 1000MinHeapT*MinOut=newT/ MinOut = iTMinSum0; / ifor i=1;i=n;i+) TMin=for j= 1;j= n;if(aj!=NoEdge(ajMin|Min=Min=ifMinNoEdgereturnNoEdge; / MinOut=MinSum+=/ E

5、-MinHeapNodeE.x = for(i= 0; i n; E.x = i+ E.s0; / xMinSum+=/ E-MinHeapNodeE.x = for(i= 0; i n; E.x = i+ E.s0; / x10E.cc0; / E.rcost= TbestcNoEdge; / / whileE.sn1) / ifE.sn2) / / / if(aE.xn-2E.xn-1!=NoEdge&aE.xn-11!=NoEdge&(E.ccaE.xn-2E.xn-1+aE.xn-11bestc|bestc=NoEdge)/ bestc=E.cc+aE.xn-2E.xn-1+aE.xn

6、-E.cc =E.lcost= E . s + + H . In s e r t( E) ;elsedeleteelse / for i= E.s +1;i n;if(aE.xE.sE.x!=NoEdge)/ 可行的孩子, Tcc= E.cc+ Trcost=E.rcost-Tbccrcostif(bbestc|bestc=NoEdge)/ / MinHeapNodeN.x = for jTbccrcostif(bbestc|bestc=NoEdge)/ / MinHeapNodeN.x = for j= 0;j n;N.xj=N.xE.s+1=N.x = N.cc =N.s = E.s+ N

7、.lcost= N.rcost=H . In s e r t( N) ; / deleteE.x; / tryH.DeleteMin(E); / E-catchOutOfBounds)break; / ifbestcNoEdgereturnNoEdge; / / 將最優(yōu)路到v1:n for(i= 0; i n; vi+1=while(true)deletetrycatch(OutOfBounds)returnwhile 循環(huán)不斷地展開E-節(jié)點,直到找到一個葉節(jié)點.當(dāng)sn1.x0n1 ,這個前綴中包含了有向圖中所有的n個頂點.sn1的活節(jié)點即為一個葉節(jié)點.算法本身的性質(zhì),while 循環(huán)不斷地展

8、開E-節(jié)點,直到找到一個葉節(jié)點.當(dāng)sn1.x0n1 ,這個前綴中包含了有向圖中所有的n個頂點.sn1的活節(jié)點即為一個葉節(jié)點.算法本身的性質(zhì),在葉節(jié)點上lcost 和cc 恰好等于葉節(jié)點對應(yīng)的旅行路徑的耗費.lcost 值都大于等于從最小堆中取出的第一個葉節(jié)點的 lcost 值,while 循環(huán)體被分別按兩種情況處理,s = n - 2E-節(jié)點,這時,E-入最小堆中,否則葉節(jié)點被刪除,并開始處理下一個E-節(jié)點E-while 循環(huán)的第二種情況中處理.首先,E-節(jié)點生成它的兩個子節(jié)點,E-x0 : s ,xi xs1n - 1點時,它的子節(jié)點可行.對于每個可行的孩子節(jié)點,將邊 的耗費加上E.cc 到

9、此孩子節(jié)點的路徑前綴( 0 : s ,x) 的耗費c c.由于每個包含此前綴的旅行路徑都必須包含離開每個剩余頂點的出邊, E-節(jié)點所生成孩子的lcost 值.如果新生成孩子的lcost 值小于目前找到的最優(yōu)旅行路徑的耗費bestc,新生成的孩子加入活節(jié)點隊列(即最小堆)中.如果有向圖沒有旅行路徑,No E d g e;否則,v 中3.回朔法解TSP 回朔法有通用解題法之稱,它采用深度優(yōu)先方式系統(tǒng)地搜索問題的所有解,基本思路是:此時,回溯到最近的活結(jié)點處,并使其成為當(dāng)前擴展結(jié)點,回溯到以這種工作方式遞歸地在解空間中搜索,旅行商問題的解空間是一棵排列樹.1,2, n類似.x=1,2,nx1:n 函

10、數(shù)TSP所作的工作主要是為調(diào)用Backtrack所需要變量初始化.由TSP調(diào)用Backtrack(2)搜索整個解空間在遞歸函數(shù)Backtrack中,當(dāng)in時,當(dāng)前擴展結(jié)點是排列樹的葉結(jié)點的父結(jié)點.此時,算法檢測圖Gxn-1 到頂點x n xn 1的邊.如果這兩條邊都存在, 當(dāng)in時,當(dāng)前擴展結(jié)點位于排列樹的第i1 層.圖G中存在從頂點xi-1到頂點xi的邊時,x1:i圖G的一條路徑,且當(dāng)x1:i 的費用小于當(dāng)前最優(yōu)值時,I層.否則將剪去相應(yīng)的子樹.當(dāng)in時,當(dāng)前擴展結(jié)點位于排列樹的第i1 層.圖G中存在從頂點xi-1到頂點xi的邊時,x1:i圖G的一條路徑,且當(dāng)x1:i 的費用小于當(dāng)前最優(yōu)值時,I層.否則將剪去相應(yīng)的子樹.中用變量x1:i的費用classTraveling* voidn,G*x,*bestx;Type*aGccbestcNoEdgevodeif(axn-1xn!=NoEdgeaxn1!=NoEdge(cc+axn-