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

1、本科实验报告课程名称： 算法设计与分析 实验项目：动态规划法求多段图问题 实验地点： 专业班级： 学号： 学生姓名： 指导教师： 实验三 动态规划法求多段图问题一、 实验目的1. 掌握动态规划算法的基本思想2. 掌握多段图的动态规划算法3. 选择邻接表或邻接矩阵方式来存储图4、分析算法求解的复杂度。二、 实验内容设G=(V,E)是一个带权有向图，其顶点的集合V被划分成k>2个不相交的子集Vi，1<i<=k，其中V1和Vk分别只有一个顶点s（源）和一个顶点t（汇）。图中所有边的始点和终点都在相邻的两个子集Vi和Vi+1中。求一条s到t的最短路线。参考讲义p136图5-24中的多

2、段图，试选择使用向前递推算法或向后递推算法求解多段图问题。三、 实验环境程序设计语言：c+编程工具：microsoft visual studio 2010四、 算法描述和程序代码#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; for(i=0;i<13;i+) f

3、or(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+) costj=0; for(j=n-1;j&

4、gt;=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 r,j,temp,min; for(j=0

5、;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() int cur=-1; int cost13

6、,d12,bcost13; int pathk; int path1k; cout<<"ttt动态规划解多段图问题"<<endl; cout<<"nn" init(cost); fgraph(cost,path,d); cout<<"输出使用向前递推算法后的最短路径:nn" for(int i=1;i<=5;i+) cout<<pathi<<" " cout<<"n" cout<<endl<<"最短路径为长度:"<<cost1<<endl; cout<<"n" cout<<"n输出使用向后递推算法后的最短路径:nn" bgraph(bcost,path1,d); for(i=1;i<=5;i+) cout<<path1i<<" " cout<<"n" cout<