動態(tài)規(guī)劃求最短路徑的兩種方法(共5頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上動態(tài)規(guī)劃1最短路線問題AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143解（1）：將上圖該畫成下圖：123456789101111213452368775845348435623143記a（1,2）=4，a(1,3)=5，依次類推，表示每個點和值的關(guān)系。逆序遞推方程：如圖各狀態(tài)：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1階段第2階段第3階段第4階段第5階段狀態(tài)1狀態(tài)2狀態(tài)3狀態(tài)4狀態(tài)5狀態(tài)6逆序遞推，找出上一個狀態(tài)到下一階段的最小路徑值。例如，當K=4時，狀態(tài)它們到

2、F 點需經(jīng)過中途點E，需一一分析從E 到 F的最短路：先說從D1到F 的最短路有兩種選擇：經(jīng)過 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,in

3、f 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,in

4、f,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

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)運行結(jié)果為：s8 = 7 s9 = 5 s10 = 5 s4 = 12 s5 = 10 s6 = 8 s7 = 9 s2 =13s3 = 15 s1 = 17結(jié)果分析：s表示每個點到終點的最短距離，那么最短路程為17。依據(jù)數(shù)據(jù)從圖中可推出最短路徑為：解（2）：運用Floyd算法求取動態(tài)規(guī)劃中最短距離及路線。MATLAB程序：a=0,4,5,inf,inf,inf,inf,inf,inf,inf,inf,

6、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,

7、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);w4=pat