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

1、1.最短路線問題動態(tài)規(guī)劃83365A3F5C3741ED34DiBiD26一、4C242Ci534C4解(1):將上圖該畫成下圖:記a(1,2)=4,a(1,3)=5,依次類推，表示每個點和值的關(guān)系逆序遞推方程：工(用)=嗖dk(sk，Uk)+fkr(Sk+1)k=5,4,3,2,1Jkf6(s6)=0如圖各狀態(tài):逆序遞推，找出上一個狀態(tài)到下一階段的最小路徑值。例如，當(dāng)K=4時，狀態(tài)S4=Di,D2,D3它們到F點需經(jīng)過中途點E,需一一分析從E到F的最短路：先說從D1到F的最短路有兩種選擇：經(jīng)過E1,E2,比較最短。f4（Di）=mind4（Di,E）f5（Ei）,d4（Di,E2）f5（E2

2、）=min34,53=7.這說明由D1到F的最短距離為7,其路徑為D1t曰7F.a=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,inf,infinf,6,7,inf,inf,0,inf,inf,3,4,inf,inf,infinf,in

3、f,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,inf,0,3inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,4,3,0;s8=min(a(8,11)+a

4、(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)+

5、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結(jié)果分析：s表示每個點到終點的最短距離，那么最短路程為17。依據(jù)數(shù)據(jù)從圖中可才t出最短路徑為：AtBtC2TD2TE?tF解(2):運用Floyd算法求取動態(tài)規(guī)劃中最短距離及路線。MATLA醒序：a=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,i

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

7、finf,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:nforj=1:nifD(i,j)=infpath(i,j)=j;end;end;end;fork=1:nfori=1:nforj=1:nifD(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=path(w3,13);w5