問題的幾種算法的分析

1、摘要本文分析比較了tsp問題的動態(tài)規(guī)劃算法，分支界限法，近似等算法。分析了旅行商問題的時間度特點，針對啟發(fā)式算法求解旅行商問題中存在的一些問題提出了改進算法。此算法將群體分為若干小子集，并用啟發(fā)式交叉算子，以較好利用父代個體的有效信息，達到快速收斂的效果，實驗表明此算法能提高尋優(yōu)速度，解得質(zhì)量也有所提高。關鍵詞： 旅行商問題 TSP Abstractthis paper analyzed the time complexity of traveling salesman problem,then put forward some imprivement towards the genetic

2、algorithm for solving this problen: divding the population into some small parent individual well.so it can quickly get into convergence, the experimental result indicates the impwoved algorithm can accelerate the apeed of finding solution and improve the precision.Keywords traveling salesman proble

3、m; genetic algorithm; subset; henristic crossover operator目錄1、 摘要-12、 Abstract-13、 Tsp問題的提法-24、 回溯法求Tsp問題-35、 分支限界法求Tsp問題-76、 近似算法求解Tsp問題-107、 動態(tài)規(guī)劃算法解Tsp問題-12引言tsp問題剛提出時，不少人都認為很簡單。后來，人們實踐中才逐步認識到，這個問題只是敘述簡單，易于為人所理解而其計算復雜性卻是問題的輸入規(guī)模的指數(shù)函數(shù)，屬于NP完全問題。Tsp問題的實現(xiàn)思想已被應用到交通，管理等很多領域所以有必要探討Tsp問題的算法。這里給出Tsp問題的動態(tài)規(guī)劃算

4、法，回溯算法，分支限界法，近似算法，和改進的啟發(fā)式算法，以及它們之間的分析比較。 正文：旅行售貨員問題的提法是：某售貨員要到若干城市去推銷商品，已知各城市之間的路程（或旅費）。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一遍，最后回到駐地的路線，使總的路程（或旅費）最小。 設G=(V,E) 是一個帶權(quán)圖。圖中各邊的費用(權(quán))為正數(shù)。圖中的一條周游路線是包括V中的每個頂點在內(nèi)的一條回路。周游路線的費用是這條路線上所有邊的費用之和。旅行售貨員問題要在圖G中找到費用最小的周游路線。1234 圖1-1： 回溯法：（1）回溯法的基本思想：確定了解空間的組織結(jié)構(gòu)后，回溯法從開始結(jié)點（根結(jié)點）出發(fā)，以深度優(yōu)先方式搜

5、索整個解空間。這個開始結(jié)點成為活結(jié)點，同時也成為當前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點即成為新的活結(jié)點，并為當前擴展結(jié)點。如果在當前的擴展結(jié)點處不能再向縱深方向移動，則當前擴展結(jié)點就成為死結(jié)點。此時，應往回移動（回溯）至最近的一個活結(jié)點處，并使這個活結(jié)點成為當前的擴展結(jié)點?；厮莘ㄒ赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已無活結(jié)點時為止。回溯法搜索解空間樹時，通常采用兩種則略避免無效搜索，提高回溯法的搜索效率。其一是用約束函數(shù)在擴展結(jié)點處減去不滿足約束的子數(shù)；其二是用界限函數(shù)剪去得不到最優(yōu)解的子數(shù)。這兩類函數(shù)統(tǒng)稱為剪支函數(shù)。 （2）回溯法解tsp問題：

6、旅行售貨員問題的解空間可以組織成一棵樹，從書的根結(jié)點到任一葉結(jié)點的路徑定義了圖G的一條周游路線。圖5-3是當n=4時解空間樹的示例。其中從根結(jié)點A到葉結(jié)點L的路徑上邊的標號組成一條周游路線1，2，3，4，1。而從根結(jié)點A到葉結(jié)點O的路徑則表示周游路線1，3，4，2，1.圖G的每一條周游路線都恰好對應于解空間樹中一條從根結(jié)點到葉結(jié)點的路徑。因此，解空間樹中葉結(jié)點個數(shù)為【（n-1）!】。圖1-2：A QPONMLKJIHGFECDB 12 4 3 4 2 4 2 34 3 4 2 3 2對于圖1-2的圖G，用回溯法找最小費用路線時，從解空間樹的根結(jié)點A出發(fā)，搜索至B,C,F,L.在葉結(jié)點L處記錄找

7、到的周游路線1，2，3，4，1，該周游路線的費用為59.從葉結(jié)點L返回至最近活結(jié)點F處。由于F處已沒有可擴展結(jié)點。算法又返回到結(jié)點C處。結(jié)點C成為新擴展結(jié)點，由新擴展結(jié)點，算法再移至結(jié)點G后又移至結(jié)點M，得到周游路線1，2，4，3，1，其費用為66.這個費用不比已有周游路線1，2，3，4，1的費用更小。因此舍棄該結(jié)點。算法又依次返回至結(jié)點G，C，B。從結(jié)點B，算法繼續(xù)搜索至結(jié)點D，H，N。在葉結(jié)點N處，相應的周游路線1，23，2，4，1的費用為25.它是當前找到的最好的一條周游路線。從結(jié)點N算法返回至結(jié)點H，D，然后在從結(jié)點D開始D開始繼續(xù)向縱深搜索至結(jié)點O。以此方法算法繼續(xù)搜索遍整個解空間，

8、最終得到最小費用周游路線1，3，2，4，1.在遞歸算法Backtrack中，當i=n時，當前擴展結(jié)點是排列數(shù)的葉結(jié)點的父結(jié)點。此時算法檢測圖G是否存在一條從頂點x【n-1到頂點xn的邊和一條從頂點xn到頂點1的邊如果這兩條邊都存在，則找到一條旅行售貨員回路。此時算法還需要判斷這條回路的費用是否優(yōu)于已找到的當前最優(yōu)回路的費用bustc。如果是則必須更新當前最優(yōu)值bestc和當前最優(yōu)解bestx。當i<n時，當前擴展結(jié)點位于排列樹的第i-1層。圖G中存在從頂點xi-1到頂點xi的邊時，xl,:i構(gòu)成圖G的一條路徑，且當x;:i的費用小于當前最優(yōu)值時算法進入排列樹的第i層，否則將剪去相應的子數(shù)

9、。算法中用變量cc記錄當前路徑x【l:i的費用。解旅行售貨員問題的回溯算法可描述如下：Template<class Type>Class Traveling friend Type tSP(int * *,int,int,Type); private:void Backtrack(int i); int n, *x, *bestx;Type* *a, cc, bestx;Type * *a, cc, bestc, NoEdge;Template<class Type>Void Traveling<Type>:Backtrack(int i)If(i=n)If

10、(axn-1)xn!=NoEdge&&axn1!=N0Edge&&(cc+axn-1xn+axn1<best|bestc=NoEdge)for(int j=1;j<=n;j+)bestxj=xj;bestc=cc+axn-1xn+axn1;elsefor(int j=i;j<=n;j+)if(axi-1xj!=NoEdge&&(cc+axi-1xj<bestc|bestc=NoEdge)Swap(xi,xj;cc+=axi-1xi;Backtrack(i+10;cc-=axi-1xi;swap(xi,xj);分支界限法：（

11、1）分支界限法的基本思想：分支界限法以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)勢的方式搜索問題的解空間樹。問題的解空間樹是表示問題解空間的一棵有序樹，常見的有子集樹和排列樹。在搜索問題的解空間樹時，分支界限法與回溯法的主要區(qū)別在于他們對當前擴展結(jié)點所采用的擴展方式不同。在分支界限法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點。活結(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導致不可行解或?qū)е路亲顑?yōu)解得兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。此后，從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。（2）從活結(jié)點表

12、中選擇下一個擴展結(jié)點的不同方式導致不同的分支界限法。最常用的有兩種方式1.方式隊列式（FIFO）分支界限法 隊列式分支界限法將活結(jié)點組織成一個隊列，并按隊列的先進先出原則選擇下一個結(jié)點為當前擴展結(jié)點。2優(yōu)先隊列式分支界限法優(yōu)先隊列式的分支界限法將活結(jié)點表組織成一個優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當前擴展結(jié)點。（3）分支法解tsp問題：考察4城市旅行售貨員的例子，如圖5-3所示，該問題的解空間樹是一棵排列樹。解次問題的隊列式分支界限法以排列樹中結(jié)點B作為初始擴展結(jié)點。此時，活結(jié)點隊列為空。由于從圖G的頂點1到頂點2，3和4均有邊相連，所以結(jié)點B的兒子結(jié)點C，

13、D，E均為可行結(jié)點，它們被加入到活結(jié)點隊列中，并舍去當前擴展結(jié)點B。當前活結(jié)點隊列中的隊首結(jié)點C成為下一個擴展結(jié)點。由于圖G的頂點2到頂點3和4有邊相連，故結(jié)點C的2個兒子結(jié)點F和G均為可行結(jié)點，從而被加入到活結(jié)點隊列中。接下來，結(jié)點D和結(jié)點E相繼成為擴展結(jié)點而被擴展。此時活結(jié)點隊列中的結(jié)點依次是F，G，H，I，J，K。算法描述：算法開始時創(chuàng)建一個最小堆，用于表示活結(jié)點優(yōu)先隊列。堆中每個結(jié)點的子樹費用的下界lcost值是優(yōu)先隊列的優(yōu)先級。接著算法計算出圖中每個頂點的最小費用出邊并用minout記錄。如果所給的有向圖中某個頂點沒有出邊，則該圖不可能有回路，算法即告結(jié)束。如果每個頂點都有出邊，則根

14、據(jù)計算出的minout作算法初始化。 算法的while循環(huán)體完成對排列樹內(nèi)部結(jié)點的擴展。對于當前擴展結(jié)點，算法分2種情況進行處理：1、首先考慮s=n-2的情形，此時當前擴展結(jié)點是排列樹中某個葉結(jié)點的父結(jié)點。如果該葉結(jié)點相應一條可行回路且費用小于當前最小費用，則將該葉結(jié)點插入到優(yōu)先隊列中，否則舍去該葉結(jié)點。2、當s<n-2時，算法依次產(chǎn)生當前擴展結(jié)點的所有兒子結(jié)點。由于當前擴展結(jié)點所相應的路徑是x0:s，其可行兒子結(jié)點是從剩余頂點xs+1:n-1中選取的頂點xi，且(xs，xi)是所給有向圖G中的一條邊。對于當前擴展結(jié)點的每一個可行兒子結(jié)點，計算出其前綴(x0:s，xi)的費用cc和相應的

15、下界lcost。當lcost<bestc時，將這個可行兒子結(jié)點插入到活結(jié)點優(yōu)先隊列中。 算法中while循環(huán)的終止條件是排列樹的一個葉結(jié)點成為當前擴展結(jié)點。當s=n-1時，已找到的回路前綴是x0:n-1，它已包含圖G的所有n個頂點。因此，當s=n-1時，相應的擴展結(jié)點表示一個葉結(jié)點。此時該葉結(jié)點所相應的回路的費用等于cc和lcost的值。剩余的活結(jié)點的lcost值不小于已找到的回路的費用。它們都不可能導致費用更小的回路。因此已找到的葉結(jié)點所相應的回路是一個最小費用旅行售貨員回路，算法可以結(jié)束。 算法結(jié)束時返回找到的最小費用，相應的最優(yōu)解由數(shù)組v給出。 近似算法： 近似算法解旅行售貨員問題

16、：問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)E有一非負整數(shù)費用c(u,v)。要找出G的最小費用哈密頓回路。旅行售貨員問題的一些特殊性質(zhì)：比如，費用函數(shù)c往往具有三角不等式性質(zhì)，即對任意的3個頂點u,v,wV，有：c(u,w)c(u,v)+c(v,w)。當圖G中的頂點就是平面上的點，任意2頂點間的費用就是這2點間的歐氏距離時，費用函數(shù)c就具有三角不等式性質(zhì)。對于給定的無向圖G，可以利用找圖G的最小生成樹的算法設計找近似最優(yōu)的旅行售貨員回路的算法。 void approxTSP (Graph g) (1)選擇g的任一頂點r； (2)用Prim算法找出帶權(quán)圖g的一棵以r為根的最小

17、生成樹T； (3)前序遍歷樹T得到的頂點表L； (4)將r加到表L的末尾，按表L中頂點次序組成回路H，作為計算結(jié)果返回； 當費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。 在費用函數(shù)不一定滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解TSP問題的多項式時間近似算法，除非P=NP。換句話說，若PNP，則對任意常數(shù)>1，不存在性能比為的解旅行售貨員問題的多項式時間近似算法。(b)表示找到的最小生成樹T；(c)表示對T作前序遍歷的次序；(d)表示L產(chǎn)生的哈密頓回路H；(e)是G的一個最小費用旅行售貨員回路。 動態(tài)規(guī)劃解tsp問題：由于貨郎擔

18、問題經(jīng)過的路線是一條經(jīng)過所有城市的閉合回路，因此從哪一點出發(fā)是無所謂的，因此不妨設從城市1出發(fā)。問題的動態(tài)規(guī)劃模型構(gòu)造如下：階段k：已經(jīng)歷過的城市個數(shù)，包括當前所在的城市。k=1, 2, , n , n+1，k=1表示出發(fā)時位于起點，k=n+1表示結(jié)束時回到終點。狀態(tài)變量：xk=(i, Sk)，其中i表示當前所在的城市，Sk表示尚未訪問過的城市的集合。很明顯 S1=2,3,n，Sn=Sn+1=F其中F表示空集。并且有 xn=(i, F) i=2,3,n， xn+1=(1, F)決策變量：dk=( i , j )，其中i為當前所在的城市，j為下一站將要到達的城市。狀態(tài)轉(zhuǎn)移方程：若當前的狀態(tài)為 x

19、k=( i ,Sk)采取的決策為 dk=( i , j )則下一步到達的狀態(tài)為 xk+1=T(xk,dk)=( j ,Sk j)階段指標： vk(xk,dk)=Cij最優(yōu)指標函數(shù)： fk(xk)=fk(i,Sk) 表示從城市i出發(fā)，經(jīng)過Sk中每個城市一次且僅一次，最后返回城市1的最短距離。終端條件： fn+1(xn+1)=fn+1(1, F)=0對于如圖所示的一個五個城市的貨郎擔問題，求解步驟如下：對于k=5，有 f5(i,F)=minCij+f6(1,F)=Ci1 i=2,3,4,5 d5?(i,1)f5(I,F)的值列表如下：i f5(i, F)2 23 74 25 5對于k=4，有 f4

20、(i, S4)=minCij+f5(j,S5) j?S4 f4(i,S4)的值列表如下：(i,S4) j Cij S5 Cij+f5(j,S5) f4(i,S4) j*(2,3) 3 3 F 3+f5(3,F)=3+7=10 10 3(2,4) 4 5 F 5+f5(4,F)=5+2=7 7 4(2,5) 5 1 F 1+f5(5,F)=1+5=6 6 5(3,2) 2 3 F 3+f5(2,F)=3+2=5 5 2(3,4) 4 4 F 4+f5(4,F)=4+2=6 6 4(3,5) 5 6 F 6+f5(5,F)=6+5=11 11 5(4,2) 2 5 F 5+f5(2,F)=5+2=

21、7 7 2(4,3) 3 4 F 4+f5(3,F)=4+7=11 11 3(4,5) 5 3 F 3+f5(5,F)=3+5=8 8 5(5,2) 2 1 F 1+f5(2,F)=1+2=3 3 2(5,3) 3 6 F 6+f5(3,F)=6+7=13 13 3(5,4) 4 3 F 3+f5(4,F)=3+2=5 5 4對于k=3，有 f3(i,S3)=minCij+f4(j,S4) j?S3f3(i,S3)的值列表如下：(i,S3) j Cij S4 Cij+f4(j,S4) f3(i,S3) j*(2,3,4) 34 35 43 3+f4(3,4)=3+6=9*5+f4(4,3)=5

22、+11=16 9 3(2,3,5) 35 31 53 3+f4(3,5)=3+11=14*1+f4(5,3)=1+13=14* 14 3,5(2,4,5) 45 51 54 5+f4(4,5)=5+8=131+f4(5,4)=1+5=6* 6 5(3,2,4) 24 34 42 3+f4(2,4)=3+7=10*4+f4(4,2)=4+7=11 10 2(3,2,5) 25 36 52 3+f4(2,5)=3+6=9*6+f4(5,2)=6+3=9* 9 2,5(3,4,5) 45 46 54 4+f4(4,5)=4+8=126+f4(5,4)=6+5=11* 11 5(4,2,3) 23 5

23、4 32 5+f4(2,3)=5+10=154+f4(3,2)=4+5=9* 9 3(4,2,5) 25 53 52 5+f4(2,5)=5+6=113+f4(5,2)=3+3=6* 6 5(4,3,5) 35 43 53 4+f4(3,5)=4+11=15*3+f4(5,3)=3+13=16 15 3(5,2,3) 23 16 32 1+f4(2,3)=1+10=11*6+f4(3,2)=6+5=11* 11 2,3(5,2,4) 24 13 42 1+f4(2,4)=1+7=8*3+f4(4,2)=3+7=10 8 2(5,3,4) 34 63 43 6+f4(3,4)=6+6=12*3+

24、f4(4,3)=3+11=14 12 3對于k=2有(i,S2) j Cij S3 Cij+f3(j,S3) f2(i,S2) j*(2,3,4,5) 345 351 4,53,53,4 3+f3(3,4,5)=3+11=145+f3(4,3,5)=5+15=201+f3(5,3,4)=1+12=13* 13 5(3,2,4,5) 245 346 4,53,52,4 3+f3(2,4,5)=3+6=9*4+f3(4,2,5)=4+6=106+f3(5,2,4)=6+8=14 9 2(4,2,3,5) 235 543 3,52,52,3 5+f3(2,3,5)=5+14=194+f3(3,2,5

25、)=4+9=13*3+f3(5,2,3)=3+11=14 13 3(5,2,3,4) 234 163 3,42,42,3 1+f3(2,3,4)=1+9=10*6+f3(3,2,4)=6+10=163+f3(4,2,3)=3+9=12 10 2對于k=1，有 f1(1,S1)=minC1j+f2(j,S2)f1(1,S1)的值列表如下：(1,S1) j Cij S2 Cij+f2(j,S2) f1(1,S1) j*(1,2,3,4,5) 2345 2725 3,4,52,4,52,3,52,3,4 2+f2(2,3,4,5)=2+13=15*7+f2(3,2,4,5)=7+9=162+f2(4

26、,2,3,5)=2+13=15*5+f2(5,2,3,4)=5+10=15* 15 2,4,5由狀態(tài)x1=(1,2,3,4,5)開始回朔，得到 (1,2,3,4,5) j*=2 j*=5 j*=4 (2,3,4,5) (5,2,3,4) (42,3,5)j*=5 j*=2 j*=3 (5,3,4) (2,3,4) (3,2,5) j*=3 j*=3 j*=2 j*=5 (3,4) (3,4) (2,5) (5,2)j*=4 j*=4 j*=4 j*=2 (4,) (4, ) (5, ) (2, )即得到以下四條回路：(1) ààààà(2) &

27、#224;àààà(3) ààààà(4) ààààà其中(1)和(4)是同一條回路，(2)和(3)是同一條回路。容易驗證，兩條回路的長度都是15。動態(tài)規(guī)劃方法并不是解決TSP問題的一個好方法，因其占用空間和時間復雜度均較大。改進的啟發(fā)式算法：本算法將群體分成若干小子集，再進行雜交變異操作，算法運行到一定階段，當群體中最優(yōu)個體的適應值之差小于某個給定的初值時，表明解空間的搜索已經(jīng)基本完成，終止遺傳迭代。算法采用最自然的路徑編碼表示方法，適應值得大小為個體所

28、代表的路徑長度的倒數(shù)。1、分級對于給定規(guī)模的群體，按適應值大小對個體進行排序，分成若干小子集，然后在各個小子集的后代個體按適應值比列選擇一定數(shù)目的個體組成新的群體，并且把父體也放在一起競爭，避免最優(yōu)個體的遺失。這樣適應值相似的個體進行交叉變異，優(yōu)秀的個體之間可以進行局部最優(yōu)解的開采。而且對每個小子集的后代以適應值比列選擇，而不是把整個群體放在一起進行選擇，這樣可以讓群體保持一定得多樣性，不易陷入早熟狀態(tài)。 2、交叉算子交叉算子的設計是遺產(chǎn)法的核心。一個好的交叉算子應該能從父體中繼承好的遺傳性狀，逐步提高子代的適應度。同時交叉算子應能有效地搜索解空間，避免算法的過快收斂。 啟發(fā)式交叉算子如下：已知兩個父體，隨機選擇一個城市c作為起點，在兩父體中分別找到c的右邊城市，并選取兩個中距c較近的那個結(jié)點c'作為子代中c的下一個結(jié)點，且把城市結(jié)點c從父體中刪除，然后對c'再尋找離它較近的下一個結(jié)點，直到完成整路徑為止，同理，另一子代產(chǎn)生