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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上本科實(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)題一、 實(shí)驗(yàn)?zāi)康?. 掌握動(dòng)態(tài)規(guī)劃算法的基本思想2. 掌握多段圖的動(dòng)態(tài)規(guī)劃算法3. 選擇鄰接表或鄰接矩陣方式來(lái)存儲(chǔ)圖4、分析算法求解的復(fù)雜度。二、 實(shí)驗(yàn)內(nèi)容設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，其頂點(diǎn)的集合V被劃分成k>2個(gè)不相交的子集Vi，1<i<=k，其中V1和Vk分別只有一個(gè)頂點(diǎn)s（源）和一個(gè)頂點(diǎn)t（匯）。圖中所有邊的始點(diǎn)和終點(diǎn)都在相鄰的兩個(gè)子集Vi和Vi+1中。求一條s到t的最短路線。參考講

2、義p136圖5-24中的多段圖，試選擇使用向前遞推算法或向后遞推算法求解多段圖問(wèn)題。三、 實(shí)驗(yàn)環(huán)境程序設(shè)計(jì)語(yǔ)言：c+編程工具：microsoft visual studio 2010四、 算法描述和程序代碼專心-專注-專業(yè)#include <stdio.h> #include <stdlib.h> #include <conio.h> #include <iostream.h> #define MAX 100 #define n 12 #define k 5 int cnn; void init(int cost) /初始化圖 int i,j;

3、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; void fgraph(int cost,int path,int d) /使用向前遞推算法求多段圖的最短路徑 int r,j,temp,min; for(j=0;j<=n;j+)

4、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) /找到最小的r min=cjr+costr; temp=r; costj=cjtemp+costtemp; dj=temp; path1=1; pathk=n; for(j=2;j<k;j+) pathj=dpathj-1; void bgraph(int bcost,int path1,int d)/使用向后遞推算法求多段圖的最短路徑 int

5、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)<min) /找到最小的r min=crj+bcostr; temp=r; bcostj=ctempj+bcosttemp; dj=temp; path11=1; path1k=n; for(int i=4;i>=2;i-) path1i=dpath1i+1; void main() i

6、nt cur=-1; int cost13,d12,bcost13; int pathk; int path1k; cout<<"ttt動(dòng)態(tài)規(guī)劃解多段圖問(wèn)題"<<endl; cout<<"nn" init(cost); fgraph(cost,path,d); cout<<"輸出使用向前遞推算法后的最短路徑:nn" for(int i=1;i<=5;i+) cout<<pathi<<" " cout<<"n" cout<<endl<<"最短路徑為長(zhǎng)度:"<<cost1<<endl; cout<<"n" cout<<"n輸出使用向后遞推算法后的最短路徑:nn" bgraph(bcost,path1,d); for(i=1;i<=5;i+) cout<<path1i<<" " cout<<"n" cout<