實(shí)驗(yàn)三-動(dòng)態(tài)規(guī)劃法求多段圖問(wèn)題

1、精品文檔打少大號(hào)TAIWAN UNIVERSITY OF TECHNOLOGY本科實(shí)驗(yàn)報(bào)告課程名稱：算法設(shè)計(jì)與分析實(shí)驗(yàn)項(xiàng)目：動(dòng)態(tài)規(guī)劃法求多段圖問(wèn)題實(shí)驗(yàn)地點(diǎn)：專業(yè)班級(jí)：學(xué)號(hào)：學(xué)生姓名：指導(dǎo)教師：隨意編輯實(shí)驗(yàn)三 動(dòng)態(tài)規(guī)劃法求多段圖問(wèn)題1、 實(shí)驗(yàn)?zāi)康?. 掌握動(dòng)態(tài)規(guī)劃算法的基本思想2. 掌握多段圖的動(dòng)態(tài)規(guī)劃算法3. 選擇鄰接表或鄰接矩陣方式來(lái)存儲(chǔ)圖4、分析算法求解的復(fù)雜度。2、 實(shí)驗(yàn)內(nèi)容設(shè) G=（V,E） 是一個(gè)帶權(quán)有向圖，其頂點(diǎn)的集合 V 被劃分成 k2 個(gè)不相交的子集Vi ，1i=k ,其中V1和Vk分別只有一個(gè)頂點(diǎn)s （源）和一個(gè)頂點(diǎn)t （匯）。圖中所有邊的始點(diǎn)和終點(diǎn)都在相鄰的兩個(gè)子集Vi 和

2、 Vi+1 中。求一條s 到 t 的最短路線。參考講義p136 圖5-24 中的多段圖，試選擇使用向前遞推算法或向后遞推算法求解多段圖問(wèn)題。3、 實(shí)驗(yàn)環(huán)境程序設(shè)計(jì)語(yǔ)言： c+編程工具： microsoft visual studio 20104、 算法描述和程序代碼#include #include #include #include #define MAX 100#define n 12#define k 5int cnn;void init(int cost) / 初始化圖int i,j;for(i=0;i13;i+)for(j=0;j13;j+) cij=MAX;c12=9;c13=7;

3、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,intd) / 使用向前遞推算法求多段圖的最短路徑 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)/ 找到最小的

4、 r min=cjr+costr;temp=r; costj=cjtemp+costtemp;dj=temp; path1=1; pathk=n;for(j=2;jk;j+)pathj=dpathj-1;void bgraph(intbcost,intpath1,int d)/ 使用向后遞推算法求多段圖的最短路徑 int r,j,temp,min;for(j=0;j=n;j+)bcostj=0;for(j=2;j=n;j+) temp=12;min=ctempj+bcosttemp;/ 初始化最小值for(r=0;r=n;r+)if(crj!=MAX)if(crj+bcostr)=2;i-)p

5、ath1i=dpath1i+1; void main()int cur=-1;int cost13,d12,bcost13;int pathk;int path1k;coutttt 動(dòng)態(tài)規(guī)劃解多段圖問(wèn)題endl;/coutnn;init(cost);fgraph(cost,path,d);cout 輸出使用向前遞推算法后的最短路徑 :nn;for(int i=1;i=5;i+) coutpathi;coutn;coutendl 最 短 路 徑 為 長(zhǎng)度 :cost1endl;coutn;coutn 輸出使用向后遞推算法后的最短路徑:nn;bgraph(bcost,path1,d);for(i=1;i=5;i+) coutpath1i;coutn;coutendl 最 短 路 徑 為 長(zhǎng) 度 :bcost12endl;coutn;五、實(shí)驗(yàn)結(jié)果截圖旭源法文電g bug、雯轂因exe動(dòng)態(tài)規(guī)劃解多段圖問(wèn)題畬出使用向前遞推算法后