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

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

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

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

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

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

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

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

8、1中。設(shè)數(shù)組dn2n-1存放迭代結(jié)果，其中dij表示從頂點i經(jīng)過子集Vj中的頂點一次且僅一次，最后回到出發(fā)點0的最短路徑長度。3.3算法分析假設(shè)從頂點i出發(fā)，令d(i,V)表示從頂點i出發(fā)經(jīng)過V中各個頂點一次且僅一次，最后回到出發(fā)點i的最短路徑的長度，開始時，V=V-i，于是，旅行商問題的動態(tài)規(guī)劃函數(shù)為： d(i,V) = mincik + d(k,V-k) (kV) 1)d(k,) = cki (k i) 2)簡單來說,就是用遞歸表達:從出發(fā)點0到1號點,假設(shè)1是第一個,則剩下的路程就是從1經(jīng)過剩下的點最后回到0點的最短路徑. 所以當(dāng)V為空的時候, d(k,) = cki (k i), 找的

9、是最后一個點到0點的距離.遞歸求解1之后,再繼續(xù)求V之中剩下的點,最后找出min.如果按照這個思想直接做,對于每一個i都要遞歸剩下的V中所有的點,所以這樣的時間復(fù)雜度就近似于N!,其中有很多重復(fù)的工作.可以從小的集合到大的集合算,并存入一個二維數(shù)組,這樣當(dāng)加入一個節(jié)點時,就可以用到之前的結(jié)果,如四個點的情況:鄰接矩陣:node01230 53215 79237 1232912 動態(tài)填表:表中元素代表第i個節(jié)點經(jīng)過V集合中的點最后到0點的最短值.如果有多個值,取其中最小的一個.iVj01231,2(取min)1,3(取min)2,3(取min)1,2,3(

10、取min)0       c0i+div=2115 1011  c12+d23=21,c13+d32=24 2312 14 c21+d13=18,c23+d31=26  321415 c31+d12=19,c32+d21=24   這樣一共循環(huán)(2(N-1)-1)*(N-1)次,就把時間復(fù)雜度縮小到O(N*2N )的級別.核心偽代碼如下:for (i =1;i<n;i+) di0=ci0;for( j

11、=1;j<2(N-1)-1;j+) for(i=1 ; i<n ;i+)if(子集Vj中不包含i)對Vj中的每個元素k，計算diVj = mincik + dkVj-k | 每一個kVj;對V2(n-1)-1中的每個元素k,計算:d02(n-1)-1 = minc0k + dk2(n-1)-2;輸出最短路徑:d02(n-1)-1;具體代碼如下:/ TravRoadD.cpp : Defines the entry point for the console application./#include "stdafx.h"#include "window

12、s.h"#include "math.h"#include <stdio.h>#include <ctime>#include <algorithm>using namespace std;int N;int matr2020; int d2040000=0;int getmin(int *sum)int i = 0;int min = -1,k;for(;i<N;i+)if(min < 0 && sumi>0) | (sumi>0 && sumi<min)min =

13、 sumi;k = i;return min;void getJ(int jlist, int c, int n)int i = n-1,j;int tmp = 1 , result = 0;while(!jlisti)i-; j = i-1;while(jlistj)j-;if(!jlistn-1)jlisti=0;jlisti+1=1;else if(n-1-j=c)for(i=0;i<n;i+)jlisti=0;for(i=0;i<c+1;i+)jlisti=1;else int k;k=n-1-j;while(!jlistj)j-;for(i=0;j+i<n;i+)j

14、listj+i=0;for(i=0;i<=k;i+)jlistj+i+1=1;int getnextj( int j )int nextj = 0;int c=0;int jlist20=0; int i=0;int tmp = 1;while(j)if(j%2)c+;jlisti+=1;elsejlisti+=0;j/=2;getJ(jlist,c,N-1);for(i=0;i<N-1;i+) if(jlisti)nextj += tmp;tmp *= 2;return nextj;int main(int argc, char* argv)freopen("d:tes

15、t_20.txt","r",stdin);int i,j;int min;scanf("%d",&N); for(i = 0; i < N; i+) for(j = 0;j < N; j+)scanf("%d",&matrij);int V20=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=1; i<N ;i

16、+)if(!(j & ( 1<<(i-1) )int jlist20=0; int tmpres20=0;int c=0,k=j,l;while(k)if(k%2)jlistc+=1;elsejlistc+=0;k/=2;c=0;for(l=0;l<N;l+)if(jlistl)tmpresc+=matril+1 + dl+1j-(1<<l);dij = getmin(tmpres);int tmpres20=0;j = pow(2,N-1)-1;for(i=1;i<N;i+)tmpresi=matr0i + di j - (1<<(i-

17、1) );min = getmin(tmpres);d02(n-1)-1 = minmatr0k + dk2(n-1)-2;d02(n-1)-1;printf("%dn",min);getchar();return 0;3.4流程圖 開始函數(shù)IsIncluded(int x,int array3)判斷x是否包含在數(shù)組中。函數(shù)Left(int k,int array3,int V83)來實現(xiàn)V'-k 的下標(biāo)檢索。函數(shù)TSP(int d48,int c44,int V83,int n)求得路徑最小值。 J<n Y N 輸出結(jié)果 結(jié)束3.5運行結(jié)果截圖如下圖4-1圖

18、4-1第四章 物流配送網(wǎng)絡(luò)為進一步說明該方法的有效性和實用性，先將該方法運用于某物流配送網(wǎng)絡(luò)中：設(shè)某物流配送網(wǎng)絡(luò)圖由9個配送點組成,點為配送中心,為終點,試求自到圖中任何配送點的最短距離。圖中相鄰兩點的連線上標(biāo)有兩點間的距離首先根據(jù)網(wǎng)絡(luò)圖以及上面的建模方法我們可以將運輸過程劃分成三個階段，分別為：第一階段，第二階段，第三階段，顯然兩點之間直線路徑小于折線路徑階段變量用k表示；狀態(tài)變量表示k階段初可能的位置；決策表示k階段初可能選擇的路線；由后向前逐步推移計算最優(yōu)路徑：當(dāng)k=3時，由到只有一條路線，故=16，=8，=4，=14當(dāng)k=2時，出發(fā)點有三個，若從出發(fā)，只有一個選擇，至，所以=27從出發(fā)，有兩個選擇，至，所以從出發(fā)，有兩個選擇，至，所以從出發(fā)，有兩個選擇，至，所以最短路線是當(dāng)k=1時，