实验三-动态规划法求多段图问题

1、精品文档打少大号TAIWAN UNIVERSITY OF TECHNOLOGY本科实验报告课程名称：算法设计与分析实验项目：动态规划法求多段图问题实验地点：专业班级：学号：学生姓名：指导教师：随意编辑实验三 动态规划法求多段图问题1、 实验目的1. 掌握动态规划算法的基本思想2. 掌握多段图的动态规划算法3. 选择邻接表或邻接矩阵方式来存储图4、分析算法求解的复杂度。2、 实验内容设 G=（V,E） 是一个带权有向图，其顶点的集合 V 被划分成 k2 个不相交的子集Vi ，1i=k ,其中V1和Vk分别只有一个顶点s （源）和一个顶点t （汇）。图中所有边的始点和终点都在相邻的两个子集Vi 和

2、 Vi+1 中。求一条s 到 t 的最短路线。参考讲义p136 图5-24 中的多段图，试选择使用向前递推算法或向后递推算法求解多段图问题。3、 实验环境程序设计语言： 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 动态规划解多段图问题endl;/coutnn;init(cost);fgraph(cost,path,d);cout 输出使用向前递推算法后的最短路径 :nn;for(int i=1;i=5;i+) coutpathi;coutn;coutendl 最 短 路 径 为 长度 :cost1endl;coutn;coutn 输出使用向后递推算法后的最短路径:nn;bgraph(bcost,path1,d);for(i=1;i=5;i+) coutpath1i;coutn;coutendl 最 短 路 径 为 长 度 :bcost12endl;coutn;五、实验结果截图旭源法文电g bug、雯毂因exe动态规划解多段图问题畲出使用向前递推算法后