全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
动态规划1最短路线问题AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143解(1):将上图该画成下图:123456789101111213452368775845348435623143记a(1,2)=4,a(1,3)=5,依次类推,表示每个点和值的关系。逆序递推方程:如图各状态:AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6逆序递推,找出上一个状态到下一阶段的最小路径值。例如,当K=4时,状态它们到F 点需经过中途点E,需一一分析从E 到 F的最短路:先说从D1到F 的最短路有两种选择:经过 E1, E2, 比较最短。这说明由 D1 到F 的最短距离为7,其路径为a=0,4,5,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf 4,0,inf,2,3,6,inf,inf,inf,inf,inf,inf,inf 5,inf,0,inf,8,7,7,inf,inf,inf,inf,inf,inf inf,2,inf,0,inf,inf,inf,5,8,inf,inf,inf,inf inf,3,8,inf,0,inf,inf,4,5,inf,inf,inf,inf inf,6,7,inf,inf,0,inf,inf,3,4,inf,inf,inf inf,inf,7,inf,inf,inf,0,inf,8,4,inf,inf,inf inf,inf,5,4,inf,inf,inf,0,inf,inf,3,5,inf inf,inf,inf,8,5,3,8,inf,0,inf,6,2,inf inf,inf,inf,inf,inf,4,4,inf,inf,0,1,3,inf inf,inf,inf,inf,inf,inf,inf,3,6,1,0,inf,4 inf,inf,inf,inf,inf,inf,inf,5,2,3,inf,0,3 inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,4,3,0;s8=min(a(8,11)+a(11,13),a(8,12)+a(12,13);s9=min(a(9,11)+a(11,13),a(9,12)+a(12,13);s10=min(a(10,11)+a(11,13),a(10,12)+a(12,13);s4=min(a(4,8)+s8,a(4,9)+s9);s5=min(a(5,8)+s8,a(5,9)+s9);s6=min(a(6,9)+s9,a(6,10)+s10);s7=min(a(7,9)+s9,a(7,10)+s10);s2=a(2,4)+s4,a(2,5)+s5,a(2,6)+s6;s2=min(s2);s3=a(3,5)+s5,a(3,6)+s6,a(3,7)+s7;s3=min(s3);s1=min(a(1,2)+s2,a(1,3)+s3)运行结果为:s8 = 7 s9 = 5 s10 = 5 s4 = 12 s5 = 10 s6 = 8 s7 = 9 s2 =13s3 = 15 s1 = 17结果分析:s表示每个点到终点的最短距离,那么最短路程为17。依据数据从图中可推出最短路径为:解(2):运用Floyd算法求取动态规划中最短距离及路线。MATLAB程序:a=0,4,5,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf 4,0,inf,2,3,6,inf,inf,inf,inf,inf,inf,inf 5,inf,0,inf,8,7,7,inf,inf,inf,inf,inf,inf inf,2,inf,0,inf,inf,inf,5,8,inf,inf,inf,inf inf,3,8,inf,0,inf,inf,4,5,inf,inf,inf,inf inf,6,7,inf,inf,0,inf,inf,3,4,inf,inf,inf inf,inf,7,inf,inf,inf,0,inf,8,4,inf,inf,inf inf,inf,5,4,inf,inf,inf,0,inf,inf,3,5,inf inf,inf,inf,8,5,3,8,inf,0,inf,6,2,inf inf,inf,inf,inf,inf,4,4,inf,inf,0,1,3,inf inf,inf,inf,inf,inf,inf,inf,3,6,1,0,inf,4 inf,inf,inf,inf,inf,inf,inf,5,2,3,inf,0,3 inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,4,3,0;n=size(a,1);D=a;path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end; end;end;for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end; end; end;end;D(1,13)w1=path(1,13);w2=path(w1,13);w3=path(w2,13);
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 道路景观设施承诺书
- 烟草产品收款流程
- 印刷厂门窗施工合同协议书
- 健身房墙面装修合同协议
- 可持续发展成品油市场管理办法
- 基坑降水施工合同:文物保护工程
- 广告公司合同管理方案
- 建筑公司工程车辆司机聘用合同
- 通信设备维护服务合同
- 流行病的特征
- 数据清洗课件-第4章-数据采集与抽取
- 2023年新改版青岛版(六三制)四年级上册科学全册精编知识点梳理
- 小学英语-There is an old building in my school教学设计学情分析教材分析课后反思
- GB/T 16935.1-2023低压供电系统内设备的绝缘配合第1部分:原理、要求和试验
- 临床微生物学检验:实验八 肠道杆菌的检验(三)
- 23秋国家开放大学《学前教育科研方法》形考作业1-3+终考作业参考答案
- 义务教育语文“思辨性阅读与表达”学习任务群教学策略
- 新时代科学家精神(2023春)学习通超星课后章节答案期末考试题库2023年
- 中考英语命题分析课件
- 大学物理(本科理工科非物理专业)PPT完整全套教学课件
- 注塑工艺卡片
评论
0/150
提交评论