算法實(shí)驗(yàn)06動(dòng)態(tài)規(guī)劃

1、課程實(shí)驗(yàn)報(bào)告課程名稱姓名實(shí)驗(yàn)名稱算法分析與設(shè)計(jì)班級(jí)實(shí)驗(yàn)日期學(xué)號(hào)實(shí)驗(yàn)成績實(shí)驗(yàn)6:動(dòng)態(tài)規(guī)劃的應(yīng)用實(shí)驗(yàn)?zāi)康募耙笠笳页鲆粭l路徑,使得路徑上的數(shù)值和最大.要求隨機(jī)生成一個(gè)高度為實(shí)驗(yàn)內(nèi)容數(shù)塔N=4,8,16,32,分別用動(dòng)態(tài)規(guī)劃法和任一種其它方法例如蠻力法、溯法、分治法等進(jìn)行求解,分析兩種方法的時(shí)間復(fù)雜度,并畫出時(shí)間隨1 .理解動(dòng)態(tài)規(guī)劃算法的根本要素;2 .掌握動(dòng)態(tài)規(guī)劃的根本步驟；3 .掌握動(dòng)態(tài)規(guī)劃的根本思想.操作系統(tǒng)：WindowsIDE：VisualC+數(shù)塔問題從數(shù)塔的頂層出發(fā),在每一個(gè)結(jié)點(diǎn)可以選擇向左走或向右走,一直走到最底層,化的曲線圖.動(dòng)態(tài)規(guī)劃運(yùn)行過程試過程-3378929136782734

2、73151005027392991315818233054244756277576445950578036最大值為：476最大值的路徑為：3378?127100495444所用時(shí)間為：0亳秒337892?136782734731510050273929491315818233054244756277576445950578036ORJ7H生93O1OOC?運(yùn)行到一定規(guī)模：6aby449Tbd9by34b095678082879132975557833779939669915096806754858272507士9872947373347760768286987152991009556783所用

3、時(shí)間為,4毫秒729460105289353419164179439201815365653781338474479319具LEAL44FA4OA采用遞歸算法：IVJJ4/40OTD3J4441rIV86814031530451098866665703824593S11355743844959347591178855556616228453647179580559798146062552165949735551765最大路徑值為；1059所用時(shí)間為：15毫秒586110631276633930100332858121819715128361591010075565616962524486698

4、29通過分析動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程dpij=max(dpi+1j,dpi+1j+1)+dataij,最后的結(jié)果保存在dp00中,可以得出時(shí)間復(fù)雜度為：O(n),而采用遞歸的方法,運(yùn)行到規(guī)模為32的就顯得比擬吃力.#include附#include錄#include#include#include#defineMAXI000usingnamespacestd;intN;/輸入規(guī)模clock_tbegintimes,endtimes;/clock_t為clock()函數(shù)返回的變量類型doubleduration;/運(yùn)行時(shí)間計(jì)算/隨機(jī)數(shù)產(chǎn)生intnumber()inta=rand()%100+1;r

5、eturna;)/定義結(jié)構(gòu)體typedefstructintx,y;intvalue;Node/定義一個(gè)二維數(shù)組存儲(chǔ)塔NodeAMAXMAXNodeBMAXMAX/輸出函數(shù),兩重for循環(huán)輸出voidshow()for(inti=0;iN;i+)Ifor(intj=0;j=i;j+)coutAij.valuecoutendl;voidinit()srand(unsigned)time(NULL);/給一個(gè)時(shí)間種子for(inti=0;iN;i+)|for(intj=0;j=i;j+)|Aij.value=number();return;/動(dòng)態(tài)規(guī)劃函數(shù)voiddp()begintimes=clo

6、ck();/計(jì)時(shí)開始intt,x1,y1;臨時(shí)計(jì)數(shù)for(intm=0;mN;m+)/初始化B結(jié)構(gòu)體數(shù)組|for(intn=0;n=0;j-)for(inti=0;iAj+1i+1.value)/當(dāng)前數(shù)大于后邊數(shù)t=Aj+1i.value;/規(guī)戈UAji.x=j+1;Aji.y=i;else/當(dāng)前數(shù)小于后邊數(shù)t=Aj+1i+1.value;Aji.x=j+1;/規(guī)戈IAji.y=i+1;口Aji.value=Aji.value+t;endtimes=clock();/計(jì)時(shí)結(jié)束x1=A00.x;yi=A00.y;cout最大值為：A00.valueendl;cout最大值的路徑為：endl;co

7、utB00.value;for(inti=0;iN-1;i+)t=x1;coutBx1y1.value,;x1=Aty1.x;y1=Aty1.y;)coutendl;)/回溯遞歸求解,較簡單,但是時(shí)間復(fù)雜度高intMaxSum(ntl,intr)(if(l=N)returnAlr.value;elsereturnmax(MaxSum(+1,r),MaxSum(l+1,r+1)+Alr.value;)/主函數(shù)intmain()(|N=4;|doN*=2;/依次增大輸入規(guī)模init();/進(jìn)行初始化show();/進(jìn)行原始塔展示/這里是遞歸回溯法begintimes=clock();/計(jì)時(shí)開始intresult=MaxSum(0,0);endtimes=clock();/計(jì)時(shí)結(jié)束cout最大路徑值為：resultendl;/dp();/動(dòng)態(tài)規(guī)劃求解duration=1000*(double)(endtimes-begintimes)/CLKTCK/總共用時(shí)(毫秒)cout所用時(shí)間為：duration毫秒endl;/記錄實(shí)驗(yàn)結(jié)果,注意運(yùn)行一次手動(dòng)進(jìn)行數(shù)據(jù)轉(zhuǎn)移,去除數(shù)據(jù)/記錄輸入規(guī)模和時(shí)間的