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

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

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

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

4、算法或分治算法不能解決的問(wèn)題。動(dòng)態(tài)規(guī)劃算法的基本思想是：將待求解的問(wèn)題分解成若干個(gè)相互聯(lián)系的子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解； 對(duì)于重復(fù)出現(xiàn)的子問(wèn)題，只在第一次遇到的時(shí)候?qū)λM(jìn)行求解，并把答案保存起來(lái)，讓以后再次遇到時(shí)直接引用答案，不必重新求解 。動(dòng)態(tài)規(guī)劃算法將問(wèn)題的解決方案視為一系列決策的結(jié)果，與貪婪算法不同的是，在貪婪算法中，每采用一次貪婪準(zhǔn)則，便做出一個(gè)不可撤回的決策；而在動(dòng)態(tài)規(guī)劃算法中，還要考察每個(gè)最優(yōu)決策序列中是否包含一個(gè)最優(yōu)決策子序列，即問(wèn)題是否具有最優(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)用

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

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

7、間的路程。他要選定一條從駐地出發(fā)，經(jīng)過(guò)每一個(gè)城市一遍，最后回到駐地的路線，使總的路程最小，并求出最小路程。3.2算法設(shè)計(jì)內(nèi)容不同城市的路線和距離都不一樣。運(yùn)用動(dòng)態(tài)規(guī)劃算法來(lái)設(shè)計(jì)本次課程設(shè)計(jì)，考慮到對(duì)問(wèn)題進(jìn)行階段劃分和狀態(tài)的選擇。使用Left函數(shù)實(shí)現(xiàn)V'-k 的下標(biāo)檢索。根據(jù)遍歷城市的各個(gè)階段時(shí)所出現(xiàn)的情況并用不同的狀態(tài)表示出來(lái)。當(dāng)然這時(shí)的狀態(tài)必須要滿足無(wú)后向性。設(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-

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

9、是最后一個(gè)點(diǎn)到0點(diǎn)的距離.遞歸求解1之后,再繼續(xù)求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)的情況:鄰接矩陣:node01230 53215 79237 1232912 動(dòng)態(tài)填表:表中元素代表第i個(gè)節(jié)點(diǎn)經(jīng)過(guò)V集合中的點(diǎn)最后到0點(diǎn)的最短值.如果有多個(gè)值,取其中最小的一個(gè).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)次,就把時(shí)間復(fù)雜度縮小到O(N*2N )的級(jí)別.核心偽代碼如下: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)對(duì)Vj中的每個(gè)元素k，計(jì)算diVj = mincik + dkVj-k | 每一個(gè)kVj;對(duì)V2(n-1)-1中的每個(gè)元素k,計(jì)算: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流程圖 開(kāi)始函數(shù)IsIncluded(int x,int array3)判斷x是否包含在數(shù)組中。函數(shù)Left(int k,int array3,int V83)來(lái)實(shí)現(xiàn)V'-k 的下標(biāo)檢索。函數(shù)TSP(int d48,int c44,int V83,int n)求得路徑最小值。 J<n Y N 輸出結(jié)果 結(jié)束3.5運(yùn)行結(jié)果截圖如下圖4-1圖

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