动态规划求最短路径的两种方法

动态规划求最短路径的两种方法

ID:35368613

大小:110.00 KB

页数:5页

时间:2019-03-24

动态规划求最短路径的两种方法_第1页
动态规划求最短路径的两种方法_第2页
动态规划求最短路径的两种方法_第3页
动态规划求最短路径的两种方法_第4页
动态规划求最短路径的两种方法_第5页
资源描述:

《动态规划求最短路径的两种方法》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、动态规划1.最短路线问题AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143解(1):将上图该画成下图:123456789101111213452368775845348435623143记a(1,2)=4,a(1,3)=5,依次类推,表示每个点和值的关系。逆序递推方程:5如图各状态:AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6逆序递推,找出上一个状态到下一阶段的最小路径值。例如,当K=4时,状态

2、它们到F点需经过中途点E,需一一分析从E到F的最短路:先说从D1到F的最短路有两种选择:经过E1,E2,比较最短。这说明由D1到F的最短距离为7,其路径为5a=[0,4,5,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf4,0,inf,2,3,6,inf,inf,inf,inf,inf,inf,inf5,inf,0,inf,8,7,7,inf,inf,inf,inf,inf,infinf,2,inf,0,inf,inf,inf,5,8,inf,inf,inf,infinf,3,8,inf,0,inf,inf,4,5,inf,inf,i

3、nf,infinf,6,7,inf,inf,0,inf,inf,3,4,inf,inf,infinf,inf,7,inf,inf,inf,0,inf,8,4,inf,inf,infinf,inf,5,4,inf,inf,inf,0,inf,inf,3,5,infinf,inf,inf,8,5,3,8,inf,0,inf,6,2,infinf,inf,inf,inf,inf,4,4,inf,inf,0,1,3,infinf,inf,inf,inf,inf,inf,inf,3,6,1,0,inf,4inf,inf,inf,inf,inf,inf,inf,5,2,3,in

4、f,0,3inf,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(

5、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=7s9=5s10=5s4=12s5=10s6=8s7=9s2=13s3=15s1=17结果分析:s表示每个点到终点的最短距离,那么最短路程为17。依据数据从图中可推出最短路径为:5解(2):运用Floyd算法求取动态规划中最短距离及路线。MATLAB程序:a=[0,4,5,inf,inf,in

6、f,inf,inf,inf,inf,inf,inf,inf4,0,inf,2,3,6,inf,inf,inf,inf,inf,inf,inf5,inf,0,inf,8,7,7,inf,inf,inf,inf,inf,infinf,2,inf,0,inf,inf,inf,5,8,inf,inf,inf,infinf,3,8,inf,0,inf,inf,4,5,inf,inf,inf,infinf,6,7,inf,inf,0,inf,inf,3,4,inf,inf,infinf,inf,7,inf,inf,inf,0,inf,8,4,inf,inf,infinf,inf

7、,5,4,inf,inf,inf,0,inf,inf,3,5,infinf,inf,inf,8,5,3,8,inf,0,inf,6,2,infinf,inf,inf,inf,inf,4,4,inf,inf,0,1,3,infinf,inf,inf,inf,inf,inf,inf,3,6,1,0,inf,4inf,inf,inf,inf,inf,inf,inf,5,2,3,inf,0,3inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,4,3,0];n=size(a,1);D=a;path=zeros(n,n);fori=1:nfor

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。