動態(tài)規(guī)劃：旅行售貨員問題

1、xxxxxxxx大學結課論文項目動態(tài)規(guī)劃算法解決旅行售貨商問題xxxxxxxxxxxxxxxxxxxxxxxxxxxx課程名稱:院系:學生姓名:學號:指導教師:xxxxxxxxxxxxxxxxxxxxx2015年6月15日摘要:旅行商問題(TSP問題)時是指旅行家要旅行n個城市然后回到出發(fā)城市，要求各個城市經歷且僅經歷一次，并要求所走的路程最短。該問題又稱為貨郎擔問題、郵遞員問題、售貨員問題，是圖問題中最廣為人知的問題。動態(tài)規(guī)劃(dynamicprogramming)算法是解決多階段決策過程最優(yōu)化問題的一種常用方法，難度比較大，技巧性也很強。利用動態(tài)規(guī)劃算法，可以優(yōu)雅而高效地解決很多貪婪算法或

2、分治算法不能解決的問題。本次課程設計運用動態(tài)規(guī)劃解決旅行售貨員問題，動態(tài)規(guī)劃的基本思想是：把求解的問題分成許多若干階段或許多子問題，然后按順序求解各子問題。前一子問題的解，為后一子問題的求解提供了有用的信息，在求解任一子問題時列出各種可能的局部解，通過決策保留那些有可能達到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。通過圖的關系矩陣來表示個城市之間的關系，二維數(shù)組表示頂點之間的距離關系，對子問題進行求解比較，最后得出所求結果。關鍵字:旅行商問題動態(tài)規(guī)劃法圖矩陣目錄第一章緒論1.1算法介紹1.2算法應用第二章動態(tài)規(guī)劃理論知識2.1動態(tài)規(guī)劃的基本思想2.2動態(tài)規(guī)

3、劃設計步驟第三章旅行售貨員問題3.1問題描述：旅行售貨員問題3.2算法設計內容3.3算法分析3.4流程圖第四章物流配送網絡第五章結論第一章緒論1.1算法介紹動態(tài)規(guī)劃(dynamicprogramming)是解決多階段決策過程最優(yōu)化問題的一種數(shù)學方法。1951年美國數(shù)學家Bellman(貝爾曼)等人根據一類多階段決策問題的特性，提出了解決這類問題的“最優(yōu)性原理”，并研究了許多實際問題，從而創(chuàng)建了最優(yōu)化問題的一種新方法動態(tài)規(guī)劃。解決多階段決策過程最優(yōu)化問題，難度比較大，技巧性也很強。利用動態(tài)規(guī)劃算法，可以優(yōu)雅而高效地解決很多貪婪算法或分治算法不能解決的問題。動態(tài)規(guī)劃算法的基本思想是：將待求解的問題

4、分解成若干個相互聯(lián)系的子問題，先求解子問題，然后從這些子問題的解得到原問題的解；對于重復出現(xiàn)的子問題，只在第一次遇到的時候對它進行求解，并把答案保存起來，讓以后再次遇到時直接引用答案，不必重新求解。動態(tài)規(guī)劃算法將問題的解決方案視為一系列決策的結果，與貪婪算法不同的是，在貪婪算法中，每采用一次貪婪準則，便做出一個不可撤回的決策；而在動態(tài)規(guī)劃算法中，還要考察每個最優(yōu)決策序列中是否包含一個最優(yōu)決策子序列，即問題是否具有最優(yōu)子結構性質。1.2算法應用動態(tài)規(guī)劃在工程技術、管理、經濟、工業(yè)生產、軍事及現(xiàn)代控制工程等方面都有廣泛的應用，而且由于動態(tài)規(guī)劃方法有其獨特之處，在解決某些實際問題時，顯得更加方便有效

5、。由于決策過程的時間參數(shù)有離散的和連續(xù)的情況，故決策過程分為離散決策過程和連續(xù)決策過程。這種技術采用自底向上的方式遞推求值，將待求解的問題分解成若干個子問題，先求解子問題，并把子問題的解存儲起來以便以后用來計算所需要求的解。簡言之，動態(tài)規(guī)劃的基本思想就是把全局的問題化為局部的問題，為了全局最優(yōu)必須局部最優(yōu)。第二章動態(tài)規(guī)劃理論知識2.1動態(tài)規(guī)劃的基本思想把求解的問題分成許多若干階段或許多子問題，然后按順序求解各子問題。前一子問題的解，為后一子問題的求解提供了有用的信息，在求解任一子問題時列出各種可能的局部解,通過決策保留那些有可能達到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題

6、就是初始問題的解。簡言之，動態(tài)規(guī)劃的基本思想就是把全局的問題化為局部的問題，為了全局最優(yōu)必須局部最優(yōu)。2.2動態(tài)規(guī)劃設計步驟1）劃分階段：按照問題的時間或空間特征，把問題分為若干階段。這若干階段一定要是有序的或可排序的（無后向性）。2）選擇狀態(tài):將問題發(fā)展到各個階段時所出現(xiàn)的各種客觀情況用不同的狀態(tài)來表示出來。狀態(tài)的選擇要有無后向性。3）確定決策并寫出狀態(tài)轉移方程:狀態(tài)轉移就是根據上一階段的狀態(tài)和決策來導出本階段的狀態(tài)。第三章旅行售貨員問題3.1問題描述：旅行售貨員問題某售貨員要到若干城市去推銷商品，已知各城市之間的路程。他要選定一條從駐地出發(fā),經過每一個城市一遍，最后回到駐地的路線，使總的路

7、程最小，并求出最小路程。3.2算法設計內容不同城市的路線和距離都不一樣。運用動態(tài)規(guī)劃算法來設計本次課程設計，考慮到對問題進行階段劃分和狀態(tài)的選擇。使用Left函數(shù)實現(xiàn)V'-k的下標檢索。根據遍歷城市的各個階段時所出現(xiàn)的情況并用不同的狀態(tài)表示出來。當然這時的狀態(tài)必須要滿足無后向性。設計第一階段則是各頂點為空，然后給賦值。依次遍歷各城市，在TSP函數(shù)中得以實現(xiàn)。假設4個頂點分別用0、1、2、3的數(shù)字編號，頂點之間的權值放在數(shù)組c44中。首先按個數(shù)為1,2,3的順序生成1,2,3個元素的子集存放在數(shù)組V2n-1中。設數(shù)組dn2n-1存放迭代結果，其中dij表示從頂點i經過子集Vj中的頂點一次

8、且僅一次，最后回到出發(fā)點0的最短路徑長度。3.3算法分析假設從頂點i出發(fā)，令d(i,V')表示從頂點i出發(fā)經過V'中各個頂點一次且僅一次，最后回到出發(fā)點i的最短路徑的長度，開始時，V'=V_i,于是，旅行商問題的動態(tài)規(guī)劃函數(shù)為：d(i,V')=mincik+d(k,V'-k)(kuV')1)d(k,)=cki(k工i)2)簡單來說,就是用遞歸表達:從出發(fā)點0到1號點，假設1是第一個,則剩下的路程就是從1經過剩下的點最后回到0點的最短路徑.所以當V'為空的時候，d(k,)=cki(k工i)找的是最后一個點到0點的距離遞歸求解1之后，再繼續(xù)求

9、V之中剩下的點，最后找出min.如果按照這個思想直接做，對于每一個i都要遞歸剩下的V中所有的點，所以這樣的時間復雜度就近似于N!，其中有很多重復的工作.可以從小的集合到大的集合算,并存入一個二維數(shù)組，這樣當加入一個節(jié)點時，就可以用到之前的結果，如四個點的情況：鄰接矩陣：node0123053215792371232912動態(tài)填表：表中元素代表第i個節(jié)點經過V集合中的點最后到0點的最短值.如果有多個值，取其中最小的一個.iVj01231,2（取min）1,3（取min）2,3（取min）1,2,3（取min）0c0i+div'=21151011c12+d23=21,c13+d32=242

10、31214c21+d13=18,c23+d31=26321415c31+d12=19,c32+d21=24這樣一共循環(huán)（2,N-1）-1）*（N-1）次,就把時間復雜度縮小到0（N*2N）的級別.核心偽代碼如下：for(i=1;in;i+)di0=ci0;for(j=1;j2,N-1)-1;j+)for(i=1;i<n;i+)if(子集Vj中不包含i)對Vj中的每個元素k，計算diVj=mincik+dkVj-k|每一個keVj;對V2"(nT)T中的每個元素k,計算：d02"(n-1)-1=minc0k+dk2"(n-1)-2;輸出最短路徑:d02&quo

11、t;(n-1)T;具體代碼如下：/TravRoadD.cpp:Definestheentrypointfortheconsoleapplication/#include"stdafx.h"#include"windows.h"#include"math.h"#includestdio.h>#includectime#includealgorithm>usingnamespacestd;intN;intmatr2020;intd2040000=0;intgetmin(int*sum)inti二0;intmin二T,k;for

12、(;iN;i+)if(min0&&sumi0)|(sumi0&&sumimin)min=sumi;k=i;returnmin;voidgetJ(intjlist,intc,intn)inti=n-1,j;inttmp=1,result二0;while(!jlisti)i-;j=i-1;while(jlistj)j-;if(!jlistn-l)jlisti=0;jlisti+l=l;elseif(n-1-j=c)for(i=0;i<n;i+)jlisti=0;for(i=0;i<c+1;i+)jlisti=1;elseintk;k=n-1-j;whil

13、e(!jlistj)j;for(i=0;j+i<n;i+)jlistj+i=0;for(i=0;i<=k;i+)jlistj+i+1=1;intgetnextj(intj)intnextj二0;intc=0;intjlist20=0;inti=0;inttmp=1;while(j)if(j%2)C+；jlisti+=l;elsejlisti+=O;j/=2;getJ(jlist,c,NT);for(i=0;iNT;i+)if(jlisti)nextj+=tmp;tmp*=2;returnnextj;intmain(intargc,char*argv)freopen("d:

14、test_20.txt","r",stdin);inti,j;intmin;scanf("%d",&N);for(i=0;i<N;i+)for(j=0;j<N;j+)scanf("%d"，&matrij);intV20=0;for(i=0;i<N;i+)Vi=1;V0=0;for(i=1;i<N;i+)di0=matri0;for(j=1;j<pow(2,N-1)-1;j=getnextj(j)for(i=l;iN;i+)if(!(j&(1(i-1)intjlist20=

15、0;inttmpres20=0;intc=O,k=j,l;while(k)if(k%2)jlistc+=1;elsejlistc+=O;k/=2;c=0;for(l=0;l<N;l+)if(jlistl)tmpresc+=matril+1+dl+1j-(1<<l);dij=getmin(tmpres);inttmpres20=0;j=pow(2,N-1)-1;for(i=1;i<N;i+)tmpresi=matrOi+dij-(1<<(iT);min=getmin(tmpres);d02"(n-1)-1=minmatrOk+dk2“(nT)-2;d

16、02"(n-1)-1;printf("%dn",min);getchar();return0;3.4流程圖3.5運行結果截圖如下圖4-1第四章物流配送網絡為進一步說明該方法的有效性和實用性，先將該方法運用于某物流配送網絡中：設某物流配送網絡圖由9個配送點組成，點A0為配送中心，A9為終點，試求自A9到圖中任何配送點的最短距離。圖中相鄰兩點的連線上標有兩點間的距離70!912一階段A0，第二階段A1,A3,A5,A7，第三階段A2,A4,A6,A8，顯然兩點之間直線路徑小于折線路徑階段變量用k表示；狀態(tài)變量Ak表示k階段初可能的位置；決策f（Ak）表示k階段初可能選

17、擇的路線；由后向前逐步推移計算最優(yōu)路徑：當k=3時，由A2,A4,A6,A8到A9只有一條路線，故f3（A2）=16，f3A4=8,f381=4，f4）=14當k=2時，出發(fā)點有A1,A3,A5,A7三個，若從A1出發(fā)，只有一個選擇，至A2，所以f2（A1）=27從A3出發(fā)，有兩個選擇，至A2,A4，所以f(A)=min<23d(A,A)+f(A)f5+1612C32、3/2、=min<=18d(A,A)+f(A)|10+8I23434丿從A5出發(fā)，有兩個選擇，至A4,A6，所以f(A5)=min<d(A,A)+f(A)2/54、3/4、,=min<d(A,A)+f(A

18、)I25636丿16*8=1915+4|從£出發(fā)，有兩個選擇，至A，A68，所以11 +4=1512 +14Id(A,A)+f(A)f(A)=min<272/76、3/6、,=min<d(A,A)+f(A)I27838丿最短路線是A7TA6TA9當k=l時，出發(fā)點有Ao一個，若從A。出發(fā)，至A1，所以f1(A0)=31若從A0出發(fā)，至A3，所以f1(A0)=25若從A0出發(fā)，至A5，所以f1(A0)=27若從A0出發(fā)，至A7，所以f1(A0)=24由上面計算得到最優(yōu)路徑f1(A0)=24，最優(yōu)路徑為A0TA7TA6TA9由本實例我們可以總結出動態(tài)規(guī)劃的優(yōu)越性所在：(1) 求解過程，結果清晰明了；(2) 能得到一組解，有利于分析結果；(3) 易于確定全局最優(yōu)解；第五章結論本次課程設計不僅讓我鞏固了動態(tài)規(guī)劃解決問題的思想以及方法,同時還讓我學到算法中的知識得以很好地運用，很好地實現(xiàn)了學以致用。在這次課程設計中我學會了不少知識,這次動態(tài)規(guī)劃來解決旅行售貨員問題，這樣很大程度上考驗了學生對所學知識的扎實，深刻的理解以及需要很好地靈活運用動態(tài)規(guī)劃是比較難理解但同時也是