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

1、動態(tài)規(guī)劃算法設計、實驗內容編程實現(xiàn)圖示多段圖的最短路徑問題的動態(tài)規(guī)劃算法O（源代碼見附錄A）、實驗目的及環(huán)境實驗目的：1、理解動態(tài)規(guī)劃算法的概念；2、掌握動態(tài)規(guī)劃算法的基本要素；3、掌握設計動態(tài)規(guī)劃算法的步驟；4、通過應用范例學習動態(tài)規(guī)劃算法的設計技巧與策略。實驗環(huán)境：WIN7系統(tǒng)下VC+6.0環(huán)境三、實驗分析與設計采用動態(tài)規(guī)劃算法的兩個基本要素：最優(yōu)子結構性質：原問題的最優(yōu)解包含了其子問題的最優(yōu)解。子問題的重疊性質：每次產生的子問題并不總是新問題，有些子問題被反復計算多次。實驗定義：#definen12/*定義頂點數(shù)*/#definek5/*定義段數(shù)*/voidinit(intcost)/初

2、始化圖voidfgraph(intcost,intpath,intd)向前遞推算法求最短路徑voidbgraph(intbcost,intpath1,intd)向后遞推算法求最短路徑向前遞推算法實現(xiàn)：intr,j,temp,min;for(j=0;j<=n;j+)costj=0;for(j=n-1;j>=1;j-)temp=0;min=cjtemp+costtemp;初始化最小值for(r=0;r<=n;r+)if(cjr!=MAX)if(cjr+costr)<min)找到最小的rmin=cjr+costr;temp=r;costj=cjtemp+costtemp;dj

3、=temp;path1=1;pathk=n;for(j=2;j<k;j+)pathj=dpathj-1;后遞推算法與前遞推算法類似。第2頁共6頁四、實驗結果顯示五、實驗總結通過理解最優(yōu)子結構的性質和子問題重疊性質，在VC+6.0環(huán)境下實現(xiàn)動態(tài)規(guī)劃算法。動態(tài)規(guī)劃算法是由單階段的決策最優(yōu)逐步轉化為多階段的決策最優(yōu)，最后構造一個最優(yōu)解。經過反復的調試操作，程序運行才得出結果。六、附錄A#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<iostream.h>#defineMAX

4、100#definen12#definek5intcnn;voidinit(intcost)inti,j;for(i=0;i<13;i+)for(j=0;j<13;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;voidfgraph(intcost,intpath,intd)intr,j,temp,min;for(j=0;j<=n;

5、j+)costj=0;for(j=n-1;j>=1;j-)temp=0;min=cjtemp+costtemp;for(r=0;r<=n;r+)if(cjr!=MAX)if(cjr+cost門)<min)(min=cjr+costr;temp=r;)costj=cjtemp+costtemp;dj=temp;)path1=1;pathk=n;for(j=2;j<k;j+)pathj=dpathj-1;)voidbgraph(intbcost,intpath1口,intd)(intr,j,temp,min;for(j=0;j<=n;j+)bcostj=0;for(j

6、=2;j<=n;j+)(temp=12;min=ctempj+bcosttemp;for(r=0;r<=n;r+)(if(crj!=MAX)(if(crj+bcostr)<min)(min=crj+bcostr;temp=r;)bcostj=ctempj+bcosttemp;dj=temp;)path11=1;path1k=n;for(inti=4;i>=2;i-)(path1i=dpath1i+1;)voidmain()(intcur=-1;intcost13,d12,bcost13;intpathk;intpath1k;init(cost);fgraph(cost,

7、path,d);cout<<"使用向前遞推算法后的最短路徑：nrT;for(inti=1;i<=5;i+)(cout«pathi«")cout«"n"cout«endl«"最短路徑為長度："<<cost1卜<endl;cout«"n"cout«"n使用向后遞推算法后的最短路徑：nrT;bgraph(bcost,path1,d);for(i=1;i<=5;i+)(cout«path1i«")