動(dòng)態(tài)規(guī)劃算法分析實(shí)驗(yàn)報(bào)告

《動(dòng)態(tài)規(guī)劃算法分析實(shí)驗(yàn)報(bào)告》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

2、疊性質(zhì)：每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。實(shí)驗(yàn)定義：#definen12/*定義頂點(diǎn)數(shù)*/#definek5/*定義段數(shù)*/voidinit(intcost[])//初始化圖voidfgraph(intcost[],intpath[],intd[])向前遞推算法求最短路徑voidbgraph(intbcost[],intpath1[],intd[])向后遞推算法求最短路徑向前遞推算法實(shí)現(xiàn)：{intr,j,temp,min;for(j=0;j<=n;j++)cost[j]=0;for(j

3、=n-1;j>=1;j--){temp=0;min=c[j][temp]+cost[temp];//初始化最小值for(r=0;r<=n;r++){if(c[j][r]!=MAX){if((c[j][r]+cost[r])

4、算法與前遞推算法類似。第6頁共6頁三、實(shí)驗(yàn)結(jié)果顯示四、實(shí)驗(yàn)總結(jié)通過理解最優(yōu)子結(jié)構(gòu)的性質(zhì)和子問題重疊性質(zhì)，在VC++6.0環(huán)境下實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法。動(dòng)態(tài)規(guī)劃算法是由單階段的決策最優(yōu)逐步轉(zhuǎn)化為多階段的決策最優(yōu)，最后構(gòu)造一個(gè)最優(yōu)解。經(jīng)過反復(fù)的調(diào)試操作，程序運(yùn)行才得出結(jié)果。第6頁共6頁三、附錄A#include#include#include#include#defineMAX100#definen12#definek5intc[n][n]

5、;voidinit(intcost[]){inti,j;for(i=0;i<13;i++){for(j=0;j<13;j++){c[i][j]=MAX;}}c[1][2]=9;c[1][3]=7;c[1][4]=3;c[1][5]=2;c[2][6]=4;c[2][7]=2;c[2][8]=1;c[3][6]=2;c[3][7]=7;c[4][8]=11;c[5][7]=11;c[5][8]=8;c[6][9]=6;c[6][10]=5;c[7][9]=4;c[7][10]=3;c[8][10]=5;c[8]

6、[11]=6;c[9][12]=4;c[10][12]=2;c[11][12]=5;}voidfgraph(intcost[],intpath[],intd[]){intr,j,temp,min;for(j=0;j<=n;j++)cost[j]=0;for(j=n-1;j>=1;j--){temp=0;min=c[j][temp]+cost[temp];for(r=0;r<=n;r++){if(c[j][r]!=MAX)第6頁共6頁{if((c[j][r]+cost[r])

7、cost[r];temp=r;}}}cost[j]=c[j][temp]+cost[temp];d[j]=temp;}path[1]=1;path[k]=n;for(j=2;j

8、r(r=0;r<=n;r++){if(c[r][j]!=MAX){if((c[r][j]+bcost[r])=2;i--){path1[i]=d[path1[i+1]];}