動態(tài)規(guī)劃算法分析實驗報告

1、.動態(tài)規(guī)劃算法設(shè)計一、實驗內(nèi)容編程實現(xiàn)圖示多段圖的最短路徑問題的動態(tài)規(guī)劃算法。（源代碼見附錄A）12345678111009129732811116535524644211127二、實驗?zāi)康募碍h(huán)境 實驗?zāi)康模?、理解動態(tài)規(guī)劃算法的概念； 2、掌握動態(tài)規(guī)劃算法的基本要素；3、掌握設(shè)計動態(tài)規(guī)劃算法的步驟； 4、通過應(yīng)用范例學(xué)習(xí)動態(tài)規(guī)劃算法的設(shè)計技巧與策略。實驗環(huán)境： WIN7 系統(tǒng)下VC+6.0環(huán)境三、 實驗分析與設(shè)計采用動態(tài)規(guī)劃算法的兩個基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)：原問題的最優(yōu)解包含了其子問題的最優(yōu)解。子問題的重疊性質(zhì)：每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。實驗定義：#defi

2、ne n 12 /*定義頂點數(shù)*/ #define k 5 /*定義段數(shù)*/void init(int cost ) /初始化圖void fgraph(int cost ,int path ,int d )向前遞推算法求最短路徑void bgraph(int bcost ,int path1 ,int d )向后遞推算法求最短路徑向前遞推算法實現(xiàn)： int r,j,temp,min; for(j=0;j=1;j-) temp=0; min=cjtemp+costtemp; /初始化最小值for(r=0;r=n;r+) if(cjr!=MAX) if(cjr+costr)min) /找到最小的r

3、 min=cjr+costr; temp=r; costj=cjtemp+costtemp; dj=temp; path1=1; pathk=n; for(j=2;jk;j+) pathj=dpathj-1; 后遞推算法與前遞推算法類似。四、 實驗結(jié)果顯示五、 實驗總結(jié)通過理解最優(yōu)子結(jié)構(gòu)的性質(zhì)和子問題重疊性質(zhì)，在VC+6.0環(huán)境下實現(xiàn)動態(tài)規(guī)劃算法。動態(tài)規(guī)劃算法是由單階段的決策最優(yōu)逐步轉(zhuǎn)化為多階段的決策最優(yōu)，最后構(gòu)造一個最優(yōu)解。經(jīng)過反復(fù)的調(diào)試操作，程序運行才得出結(jié)果。六、 附錄 A#include #include #include #include #define MAX 100 #defin

4、e n 12 #define k 5 int cnn; void init(int cost) int i,j; for(i=0;i13;i+) for(j=0;j13;j+) cij=MAX; c12=9; c13=7;c14=3; c15=2; c26=4; c27=2; c28=1; c36=2; c37=7; c48=11;c57=11;c58=8; c69=6; c610=5; c79=4; c710=3;c810=5;c811=6;c912=4;c1012=2;c1112=5; void fgraph(int cost,int path,int d) int r,j,temp,mi

5、n; for(j=0;j=1;j-) temp=0; min=cjtemp+costtemp; for(r=0;r=n;r+) if(cjr!=MAX) if(cjr+costr)min) min=cjr+costr; temp=r; costj=cjtemp+costtemp; dj=temp; path1=1; pathk=n; for(j=2;jk;j+) pathj=dpathj-1; void bgraph(int bcost,int path1,int d) int r,j,temp,min; for(j=0;j=n;j+) bcostj=0; for(j=2;j=n;j+) te

6、mp=12; min=ctempj+bcosttemp; for(r=0;r=n;r+) if(crj!=MAX) if(crj+bcostr)=2;i-) path1i=dpath1i+1; void main() int cur=-1; int cost13,d12,bcost13; int pathk; int path1k; init(cost); fgraph(cost,path,d); cout使用向前遞推算法后的最短路徑:nn; for(int i=1;i=5;i+) coutpathi ; coutn; coutendl最短路徑為長度:cost1endl; coutn; coutn使用向后遞推算法后的最短路徑:nn; bg