资源描述:
《动态规划求最短路径的两种方法》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
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