




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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动态规划解多段图问题畲出使用向前递推算法后
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 酒店求职简历模板范文
- 详解金属加工工艺 附材料加工制造与表面工艺(金属篇)
- 湘艺版音乐二年级下册5《老爷爷赶鹅》 教案
- 2025年医用高频仪器设备项目建议书
- 2025年水泥掺合剂项目建议书
- 2025年高精度数字测温仪表项目合作计划书
- 教育技术如何影响儿童学习行为
- 2025年电脑测深仪项目建议书
- 教育数字化转型中的教师激励机制研究
- 医疗教育中心理引导的作用机制
- 业务佣金提成协议书模板
- GB/T 29469-2024洁净室及相关受控环境性能及合理性评价
- 国家开放大学《城市管理学》作业-“城市病”表现及其治理
- 甄嬛传电子版剧本第01-10集
- 【中国信科-中信科移动】2023星地融合通信白皮书
- 厨师中暑防范知识讲座
- 中建测评2024二测题库及答案
- 水质检测员年终总结
- 公司期货交易及风险控制管理制度
- 娃哈哈私域代运营方案规划
- 阻塞性睡眠呼吸暂停低通气综合征的护理查房
评论
0/150
提交评论