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

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

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

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

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

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

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

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

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

9、V之中剩下的點(diǎn)，最后找出min.如果按照這個(gè)思想直接做，對(duì)于每一個(gè)i都要遞歸剩下的V中所有的點(diǎn)，所以這樣的時(shí)間復(fù)雜度就近似于N!，其中有很多重復(fù)的工作.可以從小的集合到大的集合算,并存入一個(gè)二維數(shù)組，這樣當(dāng)加入一個(gè)節(jié)點(diǎn)時(shí)，就可以用到之前的結(jié)果，如四個(gè)點(diǎn)的情況：鄰接矩陣：node0123053215792371232912動(dòng)態(tài)填表：表中元素代表第i個(gè)節(jié)點(diǎn)經(jīng)過V集合中的點(diǎn)最后到0點(diǎn)的最短值.如果有多個(gè)值，取其中最小的一個(gè).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）次,就把時(shí)間復(fù)雜度縮小到0（N*2N）的級(jí)別.核心偽代碼如下：for(i=1;in;i+)di0=ci0;for(j=1;j2,N-1)-1;j+)for(i=1;i<n;i+)if(子集Vj中不包含i)對(duì)Vj中的每個(gè)元素k，計(jì)算diVj=mincik+dkVj-k|每一個(gè)keVj;對(duì)V2"(nT)T中的每個(gè)元素k,計(jì)算：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運(yùn)行結(jié)果截圖如下圖4-1第四章物流配送網(wǎng)絡(luò)為進(jìn)一步說明該方法的有效性和實(shí)用性，先將該方法運(yùn)用于某物流配送網(wǎng)絡(luò)中：設(shè)某物流配送網(wǎng)絡(luò)圖由9個(gè)配送點(diǎn)組成，點(diǎn)A0為配送中心，A9為終點(diǎn)，試求自A9到圖中任何配送點(diǎn)的最短距離。圖中相鄰兩點(diǎn)的連線上標(biāo)有兩點(diǎn)間的距離70!912一階段A0，第二階段A1,A3,A5,A7，第三階段A2,A4,A6,A8，顯然兩點(diǎn)之間直線路徑小于折線路徑階段變量用k表示；狀態(tài)變量Ak表示k階段初可能的位置；決策f（Ak）表示k階段初可能選

17、擇的路線；由后向前逐步推移計(jì)算最優(yōu)路徑：當(dāng)k=3時(shí)，由A2,A4,A6,A8到A9只有一條路線，故f3（A2）=16，f3A4=8,f381=4，f4）=14當(dāng)k=2時(shí)，出發(fā)點(diǎn)有A1,A3,A5,A7三個(gè)，若從A1出發(fā)，只有一個(gè)選擇，至A2，所以f2（A1）=27從A3出發(fā)，有兩個(gè)選擇，至A2,A4，所以f(A)=min<23d(A,A)+f(A)f5+1612C32、3/2、=min<=18d(A,A)+f(A)|10+8I23434丿從A5出發(fā)，有兩個(gè)選擇，至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ā)，有兩個(gè)選擇，至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當(dāng)k=l時(shí)，出發(fā)點(diǎn)有Ao一個(gè)，若從A。出發(fā)，至A1，所以f1(A0)=31若從A0出發(fā)，至A3，所以f1(A0)=25若從A0出發(fā)，至A5，所以f1(A0)=27若從A0出發(fā)，至A7，所以f1(A0)=24由上面計(jì)算得到最優(yōu)路徑f1(A0)=24，最優(yōu)路徑為A0TA7TA6TA9由本實(shí)例我們可以總結(jié)出動(dòng)態(tài)規(guī)劃的優(yōu)越性所在：(1) 求解過程，結(jié)果清晰明了；(2) 能得到一組解，有利于分析結(jié)果；(3) 易于確定全局最優(yōu)解；第五章結(jié)論本次課程設(shè)計(jì)不僅讓我鞏固了動(dòng)態(tài)規(guī)劃解決問題的思想以及方法,同時(shí)還讓我學(xué)到算法中的知識(shí)得以很好地運(yùn)用，很好地實(shí)現(xiàn)了學(xué)以致用。在這次課程設(shè)計(jì)中我學(xué)會(huì)了不少知識(shí),這次動(dòng)態(tài)規(guī)劃來解決旅行售貨員問題，這樣很大程度上考驗(yàn)了學(xué)生對(duì)所學(xué)知識(shí)的扎實(shí)，深刻的理解以及需要很好地靈活運(yùn)用動(dòng)態(tài)規(guī)劃是比較難理解但同時(shí)也是