动态规划解TSP问题.docx

用动态规划方法编程求解下面的问题：某推销员要从城市v1 出发，访问其它城市v2，v3，…，v6 各一次且仅一次，最后返回v1。D为各城市间的距离矩阵。问：该推销员应如何选择路线，才能使总的行程最短？1、变量设定阶段k：已遍历过k个结点，k=1,2…6,7。K=1表示刚从V1出发，k=7表示已回到起点V1状态变量Xk=(i，Sk)：已遍历k个结点，当前位于i结点，还未遍历的结点集合为Sk。则X1=(1，{2,3,4,5,6})，X6=(i，Φ)，X7=(1，Φ)决策变量Uk=(i，j)：已遍历k个结点，当前位于i结点，下一个结点选择j。状态转移方程：Xk+1 = T(Xk，Uk) = (j，Sk-{j})第k阶段的指标函数Vk = D[i,j]。最优指标函数Fk(Xk) = Fk(i，Sk)：已遍历k个结点，当前从i结点出发，访问Sk中的结点一次且仅一次，最后返回起点V1的最短距离。则Fk(i，Sk) = min{ D[i,j] + Fk+1(j，Sk-{j}) } 1≤k≤6F7(X7) = F7(1，Φ) = 02、分析：（1）k=6时，F6(i，Φ) = min{D[i,1] + F7(X7)} = D[i,1] i=2,3,4,5,6X6=(i，Φ)U6=(i，j)X7=(1，Φ)V6=D[i,j]F7(1，Φ)V6 + F7(X7)(2，Φ)(2，1)(1，Φ)12012=F6(2,Φ)(3，Φ)(3，1)(1，Φ)23023=F6(3,Φ)(4，Φ)(4，1)(1，Φ)34034=F6(4,Φ)(5，Φ)(5，1)(1，Φ)45045=F6(5,Φ)(6，Φ)(6，1)(1，Φ)56056=F6(6,Φ)即k=6时，对于每一种状态X6，都有唯一的决策U6。（2）k=5时，F5(i，S5) = min{D[i,j] + F6(j，Φ)}i=2,3,4,5,6X5=(i,S5)U5=(i,j)X6=(j,Φ)V5=D[i,j]F6(j,Φ)V5 + F6(X6)(2,{6}}(2,6)(6，Φ)215677=F5(2,{6})(2,{5}}(2,5)(5，Φ)254570=F5(2,{5})(2,{4}}(2,4)(4，Φ)303464=F5(2,{4})(2,{3}}(2,3)(3，Φ)182341=F5(2,{3})(3,{6})(3,6)(6，Φ)155671=F5(3,{6})(3,{5})(3,5)(5，Φ)104555=F5(3,{5})(3,{4})(3,4)(4，Φ)53439=F5(3,{4})(3,{2})(3,2)(2，Φ)191231=F5(3,{2})(4,{6})(4,6)(6，Φ)165672=F5(4,{6})(4,{5})(4,5)(5，Φ)84553=F5(4,{5})(4,{3})(4,3)(3，Φ)42327=F5(4,{3})(4,{2})(4,2)(2，Φ)321244=F5(4,{2})(5,{6})(5,6)(6，Φ)185674=F5(5,{6})(5,{4})(5,4)(4，Φ)103444=F5(5,{4})(5,{3})(5,3)(3，Φ)112334=F5(5,{3})(5,{2})(5,2)(2，Φ)271239=F5(5,{2})(6,{5})(6,5)(5，Φ)124557=F5(6,{5})(6,{4})(6,4)(4，Φ)203454=F5(6,{4})(6,{3})(6,3)(3，Φ)162339=F5(6,{3})(6,{2})(6,2)(2，Φ)221234=F5(6,{2})即k=时，对于每一种状态X5，都有唯一决策U5。（3）k=4时，F4(i,S4) = min(D[i,j] + F5(j,S5) ) i=2,3,4,5,6X4=(i,S4)U4=(i,j)X5=(j,S5)V4=D[i,j]F5(j,S5)V4 + F5(j,S5)(2,{3,4})(2,3)(3,{4})183957=F4(2,{3,4})(2,4)(4,{3})302757=F4(2,{3,4})(2,{4,5})(2,4)(4,{5})305383(2,5)(5,{4})254469=F4(2,{4,5})(2,{5,6})(2,5)(5,{6})257499(2,6)(6,{5})215778=F4(2,{5,6})(2,{3,5})(2,3)(3,{5})185573(2,5)(5,{3})253459=F4(2,{3,5})(2,{3,6})(2,3)(3,{6})187189(2,6)(6,{3})213960=F4(2,{3,6})(2,{4,6})(2,4)(4,{6})3072102(2,6)(6,{4})215475=F4(2,