摘要本文分析比較了tsp問的動態規劃算法分支界限法，近似等算法。分析了旅行商問題的時間度特點對發式算求解旅行商問題中存在的一些問題提出了改進算法算法將群體分為若干小子集并用啟發式交叉算子較好利用父代個體的有效信息達到快速收斂的效果，實驗表明此算法能提高尋優速度，解得質量也有所提高。關鍵詞：旅行商問題TSPAbstractthisanalyzedthecomplexityoftravelingproblem,thenforwardsometowardsthegeneticalgorithmforsolvingthisproblen:divdingpopulationintosomesmallparentindividualwell.soitquicklyintoconvergence,experimentalresultindicatesthealgorithmcanacceleratetheapeedoffindingsolutionandimprovetheprecision.Keywordstravelingproblem;geneticalgorithm;subset;henristiccrossoveroperator目錄1、摘要-------------------------------------------------------------12、Abstract---------------------------------------------------------13、Tsp問題的提-----------------------------------------------24、回溯法求問題-------------------------------------------35、分支限界法求問--------------------------------------76、近似算法求解問-------------------------------------107、動態規劃算法解Tsp問----------------------------------12引言tsp問剛提出時，不少人都認為很簡單。后來，人們實踐中才逐步認識到，這個問題只是敘述簡單，易于為人所理解而其計算復雜性卻是問題的輸入規模的指數函數，屬于NP完全問題。問的實現思想已被應用到交通，管理等很多領域所以有必要探討Tsp問的算法。這里給出Tsp問的動態規劃算法，回溯算法，分支限界法，近似算法，和改進的啟發式算法，以及它們之間的分析比較。正文：旅行售貨員問題的提法是：某售貨員要到若干城市去推銷商品，已知各城市之間的路程（或旅費要選定一條從駐地出發，經過每個城市一遍，最后回到駐地的路線，使總的路程（或旅費）最小。設G=(V,E)是個帶權圖。圖中各邊的費權為正數。圖中的一條周游路線是包括V中的每個頂點在內的一條回路游線的費用是這條路線上所有邊的費用之和行貨員問題要在圖G中到用最小的周游路線。圖1-1：回溯法：（回溯法的本思想定了解空間的組織結構后回溯法從開始結根點發，

以深度優先方式搜索整個解空間開結點成為活結點也成為當前的擴展結點處，搜索向縱深方向移至一個新結點個新結點即成為新的活結點并為當前擴展結點如果在當前的擴展結點處不能再向縱深方向移動當前擴展結點就成為死結點此時應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結點。回溯法以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已無活結點時為止。回溯法搜索解空間樹時通常采兩種則略避免無效搜索高回溯法的搜索效率其一是用約束函數在擴展結點處減去不滿足約束的子數是用界限函數剪去得不到最優解的子數。這兩類函數統稱為剪支函數。（）溯法解tsp問：行售貨員問題的解空間可以組織成一棵樹，從書的根結點到任一葉結點的路徑定義了圖G的條周游路線5-3是n=4時空間樹的示例中從根結點到葉結點L的徑上邊的標號組成一條周游路線12，4，。而從根結點到結點O的徑則表示周游路線，，，，圖的一條周游路線都好對應于解空間樹中一條從根結點到葉結點的路徑。因此，解空間樹中葉結點個數為）圖1-2：12342423434232對于圖1-2的圖G溯法找最小費用路線時空樹的根結點A出至B,C,F,L.在葉結點L處記錄找到的周游路線1，，，，，周游路的費用為59.從葉結點返回至最近活結點處由于F處沒有可擴展結點法又返回到結點C處結成新擴展結點由擴展結點算再移至結點后移至結點得到周游路線12431，其費用為66.這費用不比已有周游路線341的用更小。因此舍棄該結點。算法又依次返回至結點GC，B。從結點，算法繼續搜索至結點D，N。在葉結點處，相應的周游路線，，，1的用為25.它當前找到的最好一條周游路線。從結點算返回至結點D，后在從結點D開始開始繼續向縱深搜索至結點O以此方法算法繼續搜索遍整個解空間，最終得到最小費用周游路線3，，，在遞歸算法中當i=n時，當前擴展結點是排列數的葉結點的父結點。此時算法檢測圖G是否存在一條從頂點【到點x[n]的邊和一條從頂點x[n]到點的邊如果這兩條邊都存在找一條旅售貨員回路時算法還需要判斷這條回路的費用是否優于已找到的當前最優回路的費用bustc如果是則必須更新當前最優值bestc和當前最優解bestx。當i<n時前擴展結點位于排列樹的第i-1層中在從頂點xi-1]到頂點x[i]的時，x[l,:i]構圖的條路徑，且當的用于當前最優值時算法進入排列樹的第層，否則將剪去相應的子數。算法中用變量cc記當前路徑【的用。解旅行售貨員問題的回溯算法可描述如下：Template<classType>ClassTraveling{friendtSP(int**,int[],int,Type);private:voidBacktrack(inti);intn,

*x,*bestx;Type**a,cc,bestx;Type**a,cc,bestc,NoEdge;};Template<classType>VoidTraveling<Type>::Backtrack(inti){If(i==n){If(a[x[n-1]])[x[n]!=NoEdge&&a[x[n]][1]!=N0Edge&&(cc+a[x[n-1]][x[n]+a[x[n][1]<best||bestc==NoEdge)){for(intj=1;j<=n;j++)bestx[j]=x[j];bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];}}else{for(intj=i;j<=n;j++)if(a[x[i-1][x[j]]!=NoEdge&&(cc+a[x[i-1]][x[j]]<bestc||bestc==NoEdge)]{Swap(x[i],x[j];cc+=a[x[i-1]][x[[i]];Backtrack(i+10;cc-=a[x[i-1]][x[i]];swap(x[i],x[j]);}}}分支界限法：（）支限的基本思想：分支界限法以廣度優先或以最小耗費（最大效益）勢的方式搜索問題的解空間樹題的解空間樹是表示問題解空間的一棵有序樹見有子集樹和排列樹搜索問題的解空間樹時支界限法與回溯法的主要區別在于他們對當前擴展結點所采用的擴展方式不同分支界限法中一活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點一性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優解得兒子結點被舍棄余兒子結點被加入活結點表中后從活結點表中取下一結點成為當前擴展結點重復上述結點擴展過程個程一直持續到找到所需的解或活結點表為空時為止。（）活點中選擇下一個擴展結點的不同方式導致不同的分支界限法。最常的有兩種方式1.方隊列式）支界限法隊列式分支界限法將活結點組織成一個隊列隊的先進先出原則選擇下一個結點為當前擴展結點。2．優先隊列式分支界法

優先隊列式的分支界限法將活結點表組織成一個優先隊列優先隊列中規定的結點優先級選取優先級最高的下一個結點成為當前擴展結點。（）支法解tsp問：察4城市旅行售貨員的例子，如圖5-3所，該問題的解空間樹是一棵排列樹問的隊列式分支界限法以排列樹中結點作初始擴展結點，活結點隊列為空。由于從圖G的頂點1到點，和4均邊相連，所以結點B的子結點E均為可行結點，它們被加入到活結點隊列中，并舍去當前擴展結B。前活結點隊列中的隊首結點C成為下一個擴展結點。由于圖G的點2到頂點3和4有邊相連，故結點的2個子結點和G均可行結點，從而被加入到活結點隊列中。接下來，結點和點E相繼成為擴展結點而被擴展時結點隊列中的結點依次是F，K。算法描述：算法開始時創建一個最小堆于表示活結點優先隊列中個結點的子樹費用的下界lcost值優先隊列的優先級。接著算法計算出圖中每個頂點的最小費用出邊并用minout記錄如所給的有向圖中某個點沒有出邊，則該圖不可能有回路法即告結束如每個頂點都有出邊，則根據計算出的minout作法初始化。算法的循環體完成對排列樹內部結點的擴展。對于前擴展結點，算法2種況進行處理：1、首先考慮s=n-2的形，此時當前擴展結點是排列樹中某個葉結點的父結點。如果該葉結點相應一條可行回路且費用小于當前最小費用將該葉結點插入到優先隊列中則舍去該葉結點。2、當s<n-2時算法依次產生當前擴展結點的所有兒子結點。由于當前擴展結點相應的路徑是x[0:s]，可行兒子結點是從剩頂點x[s+1:n-1]選取的頂點x[i]，x[s]x[i])是所給有向圖G中一條邊當前擴展結點的每一個可行兒結點其前綴，x[i])的費用cc和相應的下界。lcost<bestc時將這個可行兒子結點插入到活結點優先隊列中。算法中循的終止條件是排列樹的一個葉結點成為當前擴展結點。當s=n-1時已找到的回路前綴是，已包含圖的所有個頂點。因此，當s=n-1時相應的擴展結點表示一個葉結點。此時該葉結點所相應的回路的費用等于c和lcost的。剩余的活結點的值小于已找到的回路的費用它們都不可能導致費用更小的回路。因此已找到的葉結點所相應的回路是一個最小費用旅行售貨員回路，算法可以結束。算法結束時返回找到的最小費用，相應的最優解由數組v給出。近似算法：近似算法解旅行售貨員問題：問題描述：給定一個完全無向圖，每一邊u,v)∈有非負整數費用c(u,v)。要找出G的小費用哈密頓回路。旅行售貨員問題的一些特殊性質：比如費用函數c往往具有三角不等式性質對意的3個頂點∈有≤當圖G中的頂點就是平面上的點，任意2頂間的費就是這2點間的歐氏距離時，費用函數c就具有三角不等式性質。對于給定的無向圖利用找圖G的最小生成樹的算法設計找近似最優的旅行售貨員回路的算法。voidapproxTSP(Graphg){(1)選擇的一點r

(2)用Prim算找出帶權圖g的一棵以為的最小生成樹；(3)前序遍歷樹得的頂點表；(4)將r加表的尾，按表中頂點次序組成回路，為計算結果返回；}當費用函數滿足三角不等式時找出的旅行售貨員回路的費用不會超過最優旅行售貨員回路費用的2倍。在費用函數不一定滿足三角不等式的一般情況下在具有常數性能比的解TSP問題的多項式時間近似算法，除非P=NP。句話說，若P≠，對任意常數，不存在性能比為ρ的旅行售貨員問題的多項式時間近似算法。(b)表示找到的最小生成樹T表對T作序遍歷的次序表產的哈密頓回路H；(e)是G的一個最小費用旅行售貨員回路。動態規劃解tsp問：由于貨郎擔問題經過的路線是一條經過所有城市的閉合回路從哪一點出發是無所謂的，因此不妨設從城市1出發。問題的動態規劃模型構造如下：階段k：經過的城市個數，包括當前所在的城市k=1,...,n,，表出發時位于起點k=n+1表結束時回到終點。狀態變量：xk=(i,，其中表當前所在的城市Sk表尚未訪問過的城市的集合。很明顯S1={2,3,...,n}，，Sn=Sn+1=F其中表空集。并且有xn=(i,F)i=2,3,...,n，xn+1=(1,F)決策變量：i，中為前所在的城市j為一站將要到達的城市。狀態轉移方程：若當前的狀態為xk=(i,Sk)采取的決策為dk=(,)則下一步到達的狀態為xk+1=T(xk,dk)=(,Sk\{j})階段指標：vk(xk,dk)=Cij最優指標函數：fk(xk)=fk(i,Sk)

表示從城市i出發，經過中個城市一次且僅一次，最后返回城市1的最短距離。終端條件：fn+1(xn+1)=fn+1(1,F)=0對于如圖3.7.1所的個五個城市的貨郎擔問題，求解步驟如下：對于k=5，有f5(i,F)=min{Cij+f6(1,F)}=Ci1i=2,3,4,5d5?(i,1)f5(I,F)的列表如下：f5(i,F)223742

55對于k=4，有f4(i,S4)=min{Cij+f5(j,S5)}j?S4f4(i,S4)的列表如下：(i,S4)jCijS5Cij+f5(j,S5)f4(i,S4)(2,{3}){3}33+f5(3,F)=3+7=10103(2,{4}){4}5+f5(4,F)=5+2=74(2,{5}){5}11+f5(5,F)=1+5=665(3,{2}){2}3(3,{4}){4}4

3+f5(2,F)=3+2=54+f5(4,F)=4+2=66

24(3,{5}){5}6

6+f5(5,F)=6+5=1111

5(4,{2}){2}5

5+f5(2,F)=5+2=7

2(4,{3}){3}4

4+f5(3,F)=4+7=1111

3(4,{5}){5}3(5,{2}){2}1

3+f5(5,F)=3+5=81+f5(2,F)=1+2=3

52(5,{3}){3}6

6+f5(3,F)=6+7=1313

3(5,{4}){4}3F對于k=3，有f3(i,S3)=min{Cij+f4(j,S4)}j?S3f3(i,S3)的列表如下：(i,S3)jCijS4

3+f5(4,F)=3+2=5Cij+f4(j,S4)f3(i,S3)

4j*(2,{3,4}){3}{4}3+f4(3,{4})=3+6=9*5+f4(4,{3})=5+11=16(2,{3,5}){3}{5}3+f4(3,{5})=3+11=14*1+f4(5,{3})=1+13=14*(2,{4,5}){4}{5}5+f4(4,{5})=5+8=131+f4(5,{4})=1+5=6*(3,{2,4}){2}{4}3+f4(2,{4})=3+7=10*4+f4(4,{2})=4+7=11(3,{2,5}){2}{5}3+f4(2,{5})=3+6=9*6+f4(5,{2})=6+3=9*(3,{4,5}){4}{5}4+f4(4,{5})=4+8=126+f4(5,{4})=6+5=11*(4,{2,3}){2}{3}5+f4(2,{3})=5+10=154+f4(3,{2})=4+5=9*(4,{2,5}){2}{5}5+f4(2,{5})=5+6=113+f4(5,{2})=3+3=6*(4,{3,5}){3}{5}4+f4(3,{5})=4+11=15*3+f4(5,{3})=3+13=16(5,{2,3}){2}{3}1+f4(2,{3})=1+10=11*6+f4(3,{2})=6+5=11*(5,{2,4}){2}{4}

359331143,55165341023692,546115549353654315316112,313

{4}{3}{5}{3}{5}{4}{4}{2}{5}{2}{5}{4}{3}{2}{5}{2}{5}{3}{3}{2}{4}{2}

1+f4(2,{4})=1+7=8*3+f4(4,{2})=3+7=1082(5,{3,4}){3}{4}63{4}{3}6+f4(3,{4})=6+6=12*3+f4(4,{3})=3+11=1412對于有(i,S2)jCijS3Cij+f3(j,S3)f2(i,S2)(2,{3,4,5}){3}{4}{5}351{4,5}{3,5}{3,4}3+f3(3,{4,5})=3+11=145+f3(4,{3,5})=5+15=201+f3(5,{3,4})=1+12=13*135(3,{2,4,5}){2}{4}{5}346{4,5}{3,5}{2,4}3+f3(2,{4,5})=3+6=9*4+f3(4,{2,5})=4+6=106+f3(5,{2,4})=6+8=142(4,{2,3,5}){2}{3}{5}543{3,5}{2,5}{2,3}5+f3(2,{3,5})=5+14=194+f3(3,{2,5})=4+9=13*3+f3(5,{2,3})=3+11=14133(5,{2,3,4}){2}{3}{4}163{3,4}{2,4}{2,3}1+f3(2,{3,4})=1+9=10*6+f3(3,{2,4})=6+10=163+f3(4,{2,3})=3+9=1210對于k=1，有f1(1,S1)=min{C1j+f2(j,S2)}的列表如下：(1,S1)jCijS2Cij+f2(j,S2)f1(1,S1)(1,{2,3,4,5}){2}{3}{4}{5}{3,4,5}{2,4,5}{2,3,5}{2,3,4}2+f2(2,{3,4,5})=2+13=15*7+f2(3,{2,4,5})=7+9=162+f2(4,{2,3,5})=2+13=15*5+f2(5,{2,3,4})=5+10=15*152,4,5由狀態x1=(1,{2,3,4,5})開回朔，得到(1,{2,3,4,5})j*=2j*=5j*=4(2,{3,4,5})(5,{2,3,4})(4{2,3,5})j*=5j*=2j*=3(5,{3,4})(2,{3,4})(3,{2,5})j*=3j*=3j*=2j*=5(3,{4})(3,{4})(2,{5})(5,{2})j*=4j*=4j*=4j*=2(4,(4,(5,Φ)(2,即得到以下四條回路：(1)(2)(3)(4)

①à②à③à④à①①à⑤à③à④à①①à④à③à⑤à①①à④à③à②à①其中和4)是一條回路和3)是同一回路。容易驗證，兩條回路的長度都是。動態規劃方法并不是解決TSP問題的一個好方法，因其占用空間和時間復雜度均較大。改進的啟發式算法：本算法將群體分成若干小子集進行雜交變異操作算法運行到一定階段當群體中最優個體的適應值之差小于某個給定的初值時明解空間的搜索已經基本完成止遺傳迭代采最自然的路徑編表示方法值大小為個體所代表的路徑長度的倒數。1、分級

對于給定規模的群體按適應值小對個體進行排序成若干小子集然后在各個小子集的后代個體按適應值比列選擇一定數目的個體組成新的群體，并且把父體也放在一起競爭，避免最優個體的遺失樣應相似的個體進行交叉變異秀個體之間可以進行局部最優解的開采且對每個小子集的后代以適應值比列選擇不是把整個群體放在一起進行選擇，這樣可以讓群體保持一定得多樣性，不易陷入早熟狀態。2交叉算子交叉算子的設計是遺產法的核心好的交叉算子應該能從父體中繼承好的遺傳性狀，逐步提高子代的適應度。同時交叉算子應能有效地搜索解空間，避免算法的過快收