则动态规划的顺序递推关系为 min&(s\j,j)+d f60(,)=d1,i=2,3,…,n,k=1,2,…,n-1 最后算出fn=1(N,1)2N={2,3,…,m},即为全程的最短距离同时 可得最优策略,即最优行走路线. 例1已知4个城市间距离如表1,求从城市1出发,经其与城 市一次且仅一次最优回到城市1的最短路与距离
则动态规划的顺序递推关系为: = = = − = − + ( , ) , 2,3, , , 1,2, , 1. ( , ) min{ ( \ , ) } 0 1 1 f i d i n k n f S i f S j j d i k j i j S k 最后算出 ,即为全程的最短距离,同时 可得最优策略,即最优行走路线. ( ,1), f n−1 N N = {2,3, ,n} 例1 已知 4个城市间距离如表1，求从城市1出发，经其与城 市一次且仅一次最优回到城市1的最短路与距离。 ( ,1), f n−1 N N ={2,3, ,n}
856 6085 7905 9780 解:由边界条件知 f6(01)=d1=0f6(,2)=ad12=66(,3)=d13=7 f6(,4)=d14=9
城 城 市 市 1 2 3 4 1234 0856 6085 7905 9780 解：由边界条件知： ( , 1 ) 0 f0 = d11 = f0 (, 2 ) = d12 = 6 f0 (, 3 ) = d13 = 7 f0 (, 4 ) = d14 = 9
856 6085 7905 9780 当k=1时,从城市1出发,经过1个城市到达城市的最短距离 为 f(S,2)=min{f0(,3)+a32,f0(4)+d4 min{7+8,9+5}=14, x2({4,2)=4 即从城市1出发,途经1个城市去城2,应先到4,再到2
城 城 市 市 1 2 3 4 1 2 3 4 0 8 5 6 6 0 8 5 7 9 0 5 9 7 8 0 当k=1时，从城市1出发，经过1个城市到达城市i的最短距离 为： ( ,2) min{ ( ,3) , ( ,4) } 1 0 32 0 d42 f S = f + d f + = min{ 7 +8,9 +5} =14, ({4},2) 4 * x2 = 即从城市1出发，途经1个城市去城2，应先到4，再到2
1234 0856 085 7905 9780 f(S,3)=mn{f0(0,2)+d23,f0(,4)+d43 mn{6+9,9+5}=14, ({4},3)=4 即从城市1出发,途经1个城市去城3,应先到4,再到3
城 城 市 市 1 2 3 4 1 2 3 4 0 8 5 6 6 0 8 5 7 9 0 5 9 7 8 0 ( ,3) min{ ( ,2) , ( ,4) } 1 0 23 0 d43 f S = f + d f + = min{ 6 +9,9 +5} =14, ({4},3) 4 * x2 = 即从城市1出发，途经1个城市去城3，应先到4，再到3