实验三-动态规划法求多段图问题讲课教案.docx

《实验三-动态规划法求多段图问题讲课教案.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验三-动态规划法求多段图问题精品文档本科实验报告课程名称：算法设计与分析实验项目：动态规划法求多段图问题实验地点：专业班级：学号：学生姓名：指导教师：收集于网络，如有侵权请联系管理员删除精品文档实验三动态规划法求多段图问题一、实验目的1.掌握动态规划算法的基本思想2.掌握多段图的动态规划算法收集于网络，如有侵权请联系管理员删除精品文档1.选择邻接表或邻接矩阵方式来存储图4、分析算法求解的复杂度。一、实验内容设G=(V,E)是一个带权有向图，其顶点的集合V被划分成k>2个不相交的子集Vi，1

2、点都在相邻的两个子集Vi和Vi+1中。求一条s到t的最短路线。参考讲义p136图5-24中的多段图，试选择使用向前递推算法或向后递推算法求解多段图问题。二、实验环境程序设计语言：c++编程工具：microsoftvisualstudio2010三、算法描述和程序代码收集于网络，如有侵权请联系管理员删除精品文档#include#include#include#include#defineMAX100#definen12#definek5intc[n][n];voidinit(intcost[])//初始

3、化图{inti,j;for(i=0;i<13;i++){for(j=0;j<13;j++){c[i][j]=MAX;}}c[1][2]=9;c[1][3]=7;c[1][4]=3;c[1][5]=2;c[2][6]=4;c[2][7]=2;c[2][8]=1;c[3][6]=2;c[3][7]=7;c[4][8]=11;c[5][7]=11;c[5][8]=8;c[6][9]=6;c[6][10]=5;c[7][9]=4;c[7][10]=3;c[8][10]=5;c[8][11]=6;c[9][12]=4;c[10][12]=2;c[11][12]=5;}voidfgraph(

4、intcost[],intpath[],intd[])//使用向前递推算法求多段图的最短路径{intr,j,temp,min;for(j=0;j<=n;j++)收集于网络，如有侵权请联系管理员删除精品文档cost[j]=0;for(j=n-1;j>=1;j--){temp=0;min=c[j][temp]+cost[temp];//初始化最小值for(r=0;r<=n;r++){if(c[j][r]!=MAX){if((c[j][r]+cost[r])

5、st[temp];d[j]=temp;}path[1]=1;path[k]=n;for(j=2;j

6、st[r])=2;i--){path1[i]=d[path1[i+1]];}}voidmain(){intcur=-1;intcost[13],d[12],bcost[13];intpath[k];intpath1[k];cout<<"ttt动态规划解多段图问题"<

7、ph(cost,path,d);cout<<"输出使用向前递推算法后的最短路径:";for(inti=1;i<=5;i++){cout<