

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
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ī)劃是比較難理解但同時也是
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年銀行反洗錢知識競賽題庫及答案(320題)
- 2025河北保定市雄安傳媒有限公司招聘10人筆試參考題庫附帶答案詳解
- 2025廣東深圳證券交易所及其下屬單位信息技術專業(yè)人員招聘筆試參考題庫附帶答案詳解
- 湖北工行面試題目及答案
- 西部計劃面試題目及答案
- 2025年合肥公交集團有限公司駕駛員招聘180人預筆試參考題庫附帶答案詳解
- 美麗新世界美容師職業(yè)的挑戰(zhàn)與機遇試題及答案
- 2024年度四川省護師類之護師(初級)題庫綜合試卷B卷附答案
- 2025山東濰坊市產業(yè)發(fā)展集團有限公司招聘53人筆試參考題庫附帶答案詳解
- 古代文學史的文化交融試題及答案
- 第6課 隋唐時期的中外文化交流 【公開課一等獎創(chuàng)新教學設計】-【教學評一體化】大單元整體教學
- 幼教培訓課件:《幼兒園思維共享的組織與實施》
- 幼兒園清明節(jié)主題班會課件
- 西安經濟技術開發(fā)區(qū)管委會招聘筆試真題2024
- 工業(yè)互聯(lián)網平臺的商業(yè)模式與盈利策略
- 2024年09月2024渤海銀行上海分行校園招聘筆試歷年參考題庫附帶答案詳解
- 2025年遼寧省遼漁集團招聘筆試參考題庫含答案解析
- 《員工招聘與選拔》課件
- 南昌起義模板
- 【MOOC】體育舞蹈與文化-大連理工大學 中國大學慕課MOOC答案
- 接處警流程培訓
評論
0/150
提交評論