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

1、第 1 頁 共 6 頁動態(tài)規(guī)劃算法 設(shè)計一、實驗內(nèi)容編程實現(xiàn)圖示多段圖的最短路徑問題的動態(tài)規(guī)劃算法。（源代碼見附錄a）二、實驗?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)境1 234567811 10912 9 7 3 2 8 116 5 3 5 5 2 4 6 4 4 2 1 11 2 7第 2 頁 共 6 頁三、 實驗分析與設(shè)計采用動態(tài)規(guī)劃算法的兩個基本要素: 最優(yōu)子結(jié)構(gòu)性質(zhì) ：原問題的最優(yōu)解包含了其子問題的最優(yōu)解. 子問題的重

2、疊性質(zhì) :每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。實驗定義：define 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 =n；j+) costj=0；for(j=n-1;j =1；j-) temp=0; min=cj temp

3、+cost temp ；/初始化最小值for（ r=0；r include stdlib。h #include conio。h include iostream 。h define max 100 #define n 12 define k 5 int cn n ; void init(int cost) int i,j ；for（i=0;i 13；i+) for(j=0 ；j13;j+) ci j=max; c12=9 ； c13=7;c1 4=3 ； c15=2；c2 6 =4； c2 7=2； c2 8=1 ；c36=2; c 3 7=7; c48 =11; c57 =11;c5 8=8

4、；c69 =6; c6 10=5; c7 9=4； c710=3; c8 10=5;c8 11=6；c9 12=4; c10 12=2; c1112=5; void fgraph(int cost ,int path ,int d ） int r,j，temp， min; for(j=0;j=1;j- ） temp=0; min=cj temp+costtemp ；for（r=0;r =n;r+) if(cj r ！=max ）第 5 頁 共 6 頁 if( （cj r+costr ）min） min=cj r+costr ；temp=r； costj=c j temp+cost temp;

5、dj=temp； path1=1；pathk=n; for(j=2 ；jk;j+ ）pathj=dpath j1 ；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+ ）temp=12; min=ctemp j +bcosttemp ；for(r=0;r=n ；r+) if(c r j!=max) if（ （c rj +bcostr ）min） min=cr j +bcostr; temp=r；bcostj=ctemp j+bcosttemp

6、 ；dj=temp; path11=1; path1k=n ；for(int i=4 ； i=2；i ) path1 i=d path1i+1; 第 6 頁 共 6 頁void main() int cur=-1 ；int cost13,d 12， bcost13 ；int pathk ; int path1k；init(cost） ; fgraph（cost,path,d); cout ”使用向前遞推算法后的最短路徑：nn; for(int i=1 ； i=5；i+ ） coutpathi ” ；coutn” ; coutendl最短路徑為長度：cost1 endl；cout n; cout n 使用向后遞推算法后的最短路徑：n” ；bgrap