動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)多段圖的最短路徑問(wèn)題算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告

1、動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)多段圖的最 短路徑問(wèn)題算法設(shè)計(jì)與分析實(shí) 驗(yàn)報(bào)告作者:日期:算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)多段圖的最短路徑問(wèn)題評(píng)分實(shí)驗(yàn)日期指導(dǎo)教師姓名專業(yè)班級(jí)學(xué)號(hào)實(shí)驗(yàn)要求1.理解最優(yōu)子結(jié)構(gòu)的問(wèn)題。有一類問(wèn)題的活動(dòng)過(guò)程可以分成若干個(gè)階段，而且在任一階段后的行為依賴于該階段的狀態(tài)，與該階段之前的過(guò)程如何達(dá)到這種狀態(tài)的方式無(wú)關(guān)。這類問(wèn)題的解決是多階段的決 策過(guò)程。在50年代，貝爾曼(Richard Bell man)等人提出了解決這類問(wèn)題的最優(yōu)化原理”,從而創(chuàng)建了最優(yōu)化問(wèn)題的一種新的算法設(shè)計(jì)方法-動(dòng)態(tài)規(guī)劃。對(duì)于一個(gè)多階段過(guò)程問(wèn)題，是否可以分段實(shí)現(xiàn)最優(yōu)決策，依賴于該問(wèn)題是否有最優(yōu)子 結(jié)構(gòu)

2、性質(zhì)，能否采用動(dòng)態(tài)規(guī)劃的方法，還要看該問(wèn)題的子問(wèn)題是否具有重疊性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)： 原問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解。子問(wèn)題重疊性質(zhì)： 每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。 問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì)是采用動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素。2.理解分段決策Bel Iman方程。每一點(diǎn)最優(yōu)都是上一點(diǎn)最優(yōu)加上這段長(zhǎng)度。即當(dāng)前最優(yōu)只與上一步有關(guān)。0,Uj minUiWj.UsUS初始值，Uj第j段的最優(yōu)值。3.一般方法1)2)3)找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征； 遞歸地定義最優(yōu)值(寫(xiě)出動(dòng)態(tài)規(guī)劃方程)； 以自底向上的方式計(jì)算出最優(yōu)值 ； 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，

3、構(gòu)造一個(gè)最優(yōu)解。4)步驟1-3是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟4可以省略，步驟3中記錄的信息也較少；若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟4,步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。二.實(shí)驗(yàn)內(nèi)容1 .編程實(shí)現(xiàn)多段圖的最短路徑問(wèn)題的動(dòng)態(tài)規(guī)劃算法。2.圖的數(shù)據(jù)結(jié)構(gòu)采用鄰接表。3.要求用文件裝入5個(gè)多段圖數(shù)據(jù)，編寫(xiě)從文件到鄰接表的函數(shù)。4.驗(yàn)證算法的時(shí)間復(fù)雜性。三程序算法多段圖算法：P r ocedure F G RAPH(E , k , n ,P)/輸入是按段的順序給結(jié)點(diǎn)編號(hào)的，有>的成本。P(1 ： k)是最小成本路徑。real C O ST(n),inte

4、geCOS T(n) < - 0for j< n1 to設(shè)r是一個(gè)這樣的結(jié)點(diǎn)cOSr( j)</P (1) < 1;P (k) < -n;f or j<-2 t o k -1 do /找路徑上的第j個(gè)節(jié)點(diǎn)/ /P (j ) <- D (P(j 1);re p eat ;endFGR AP Hr (n-1),P(kby -1,(J , r)c(j , r) + COS四程序代碼# i ncl u de < st d i o.h> #i n clude <s t dlib.h># i n c l# inc 1# defin#de f

5、 in#d e fi ne k 5 intu d e < coni o .h> ude < i ost r eam.h >e M AX 1 00e n 12/ *頂點(diǎn)數(shù)*/*段數(shù)*/n個(gè)結(jié)點(diǎn)的k段圖。E是邊集,c (i ,j )是邊i , j/,r, j,k, n/ / 計(jì)算 COSTJ )/E且使c(j,r )+ COST( r )取最小值T (r );D( J ) < -r;R e p eat / /向前對(duì) j 1進(jìn)行決策 /void?n?c n : n ;i n i t( i nt cost ) /初始化圖i,j; for(i = 0; i< 1 3;

6、 i +)r(j=0;j<13; j+ + ) ? : i : J =MAX;c 1 : : 2=9; ?c13 =7 ;c27=2; ?c： 28=1;c : 36=2;? : 37=7;c 6 : 10 = 5;9 = 4; ?c 710 =c10: 12=2; c 11 :c1：4 = 3 ；?c 1 5=2;c48=11; ?c：5 7=11;?c 隹:8: 1 0 = 5 ; ?： : 811 = 6;2 =5 ;c2:6=4：8= 8 ; ?:69= 6;c912=4v o id f gr aph( i nt c o s t,圖的最短路徑int p a th ,in t d

7、) /使用向前遞推算法求多段?or(i n t r ,j, t em p, m in;J = 0； j< =n ;j + ) ?3OStj=0；fo r (j=n 1; j>=1;J -)te m p= 0 ;?ni n=cje mp;/初始化最小值for( r = 0 丁<=n; r + +)?if(cjr ! =MA X)?if (c : jr+c o str)<mi n )?mi n =cJ r : +c ost： r:;? emp= r ;?升?Zo s t j=cj ： t e mp + co st?d :J=t e mpte mp +co st tt e m

8、p;pa th : 1= 1；p a thk =n;f or (j=2;j< k;j+ )path : j=d : pat h : j 1:;/ /找到最小的rV oid bg raph(int的最短路徑b c ost , i nt path1 , int d )/ /使用向后遞推算法求多段圖?or,temp , m in ;<=n;j+ )0 ;J <= n; j + )?i nt r ,j(J =0;Jbcostj=f or(j=2;temp= 12;mi n =ctem p j+b c ost temp;?or( r =0; r <=n ;r + + )/ /初始

9、化最小值if(c : rj!=MAX)?if (crj+ b cost r ) <min)?m i n = cr:j : +b co st :r;t emp= r;?/找到最小的rPr*s* *ny to continuDb costd ：j :j = ctemp j :=t emp ;+bco st te mp ;?orath11=at h 1 k =n;(int i=4 ;i > =2;i-)?a th1i=dpat h 1i+ 1 ；void ma i()int curint cot p a th=-1;st1 3 , d12,bc o s:k;t：13 ;int pa t

10、h1k;?:o u t < t t動(dòng)態(tài)規(guī)劃解多段圖問(wèn)題"<<endl;c out<<" n n"in it(cos t );fg raph (c os t ,pat h , d );cout<< "輸出使用向前遞推算法后的最短路徑：n n"?or( ?o ?ut< <p ath : i<<""i nt i =1; i<=5;i + + )?c o u t<<"n "? cout < < e nd 1 <<"最短路徑為長(zhǎng)度:"<< co s t 1< <e ndl ; co ut<<"n"cout << "n輸出使用向后遞推算法后的最短路徑： nn" bgrap h (bcost,pat h1, d );f or (i=1 ; i<=5;i+)II?o u t< < p a th1 i <<"cout< < "n"co u t << end l&l