实验三-动态规划法求多段图问题(共4页).docx

会员专享推荐 · 你可能也用得上更多

开通会员，畅读全站文档

本篇文档已为你保留

本篇文档价值 ~~¥35.00~~会员免费解锁

全文不限次阅读，剩余内容即刻解锁
高速下载通道，免排队、无等待
专属客服 1 对 1 答疑，优先响应
每日赠送下载券，本篇文档免费送

有 86 篇商业计划书正在上传

下载原文档

本科实验报告课程名称：算法设计与分析实验项目：动态规划法求多段图问题实验地点：专业班级：学号：学生姓名：指导教师：实验三动态规划法求多段图问题一、实验目的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中的多段图，试选择使用向前递推算法或向后递推算法求解多段图问题。三、实验环境程序设计语言：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 c[n][n];void init(int cost[])//初始化图{int i,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;}void fgraph(int cost[],int path[],int d[])//使用向前递推算法求多段图的最短路径{int r,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])<min)//找到最小的r{min=c[j][r]+cost[r];temp=r;}}}cost[j]=c[j][temp]+cost[temp];d[j]=temp;}path[1]=1;path[k]=n;for(j=2;j<k;j++)path[j]=d[path[j-1]];}void bgraph(int bcost[],int path1[],int d[])//使用向后递推算法求多段图的最短路径{int r,j,temp,min;for(j=0;j<=n;j++)bcost[j]=0;for(j=2;j<=n;j++){temp=12;min=c[temp][j]+bcost[temp];//初始化最小值for(r=0;r<=n;r++){if(c[r][j]!=MAX){if((c[r][j]+bcost[r])<min)//找到最小的r{min=c[r][j]+bcost[r];temp=r;}}}bcost[j]=c[temp][j]+bcost[temp];d[j]=temp;}path1[1]=1;path1[k]=n;for(int i=4;i>=2;i--){path1[i]=d[path1[i+1]];}}void main(){int cur=-1;int cost[13],d[12],bcost[13];int path[k];int path1[k];cout<<"\t\t\t动态规划解多段图问题"<<endl;cout<<"\n\n";init(cost);fgraph(cost,path,d);cout<<"输出使用向前递推算法后的最短路径:\n\n";for(int i=1;i<=5;i++){cout<<path[i]<<"";}cout<<"\n";cout<<endl<<"最短路径为长度:"<<cost[1]<<endl;cout<<"\n";cout<<"\n输出使用向后递推算法后的最短路径:\n\n";bgraph(bcost,path1,d);for(i=1;i<=5;i++){cout<<path1[i]<<"";}cout<<"\n";cout<<endl<<"最短路径为长度:"<<bcost[12]<<endl;cout<<"\n";}五、实验结果截图六、实验总结。