《动态规划解tsp问题》由会员分享，可在线阅读，更多相关《动态规划解tsp问题（7页珍藏版）》请在金锄头文库上搜索。
1、用动态规划方法编程求解下面的问题： 某推销员要从城市v1 出发，访问其它城市v2，v3，v6 各一次且仅一次，最后返回 v1。D为各城市间的距离矩阵。问：该推销员应如何选择路线，才能使总的行程最短？012201622561801011274516804323415105019232125301801250403020100654321vvvvvvD1、变量设定、变量设定阶段 k：已遍历过 k 个结点，k=1,26,7。K=1 表示刚从 V1 出发，k=7 表示已回到起点 V1 状态变量 Xk=(i，Sk)：已遍历 k 个结点，当前位于 i 结点，还未遍历的结点集合 为 Sk。则 X1=(1，2
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 = Di,j。 最优指标函数 Fk(Xk) = Fk(i，Sk)：已遍历 k 个结点，当前从 i 结点出发，访问 Sk 中的结点一次且仅一次，最后返回起点 V1 的最短距离。 则 Fk(i，Sk) = min Di,j + Fk+1(j，Sk-j) 1k6F7(X7) = F7(1，) = 02、分析：、分析：（1）k=6 时，F6(i，) = minDi,
3、1 + F7(X7) = Di,1 i=2,3,4,5,6X6=(i，)U6=(i，j)X7=(1，)V6=Di,jF7(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) = minDi,j + F6(j，) i=2,3,4,5,6X5=(i,S5)U5=(i,j)X6=(
4、j, )V5=Di,jF6(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，)84
5、553=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)
6、 即 k=时，对于每一种状态 X5，都有唯一决策 U5。（3）k=4 时，F4(i,S4) = min(Di,j + F5(j,S5) ) i=2,3,4,5,6 X4=(i,S4)U4=(i,j)X5=(j,S5)V4=Di,jF5(j,S5)V4 + F5(j,S5) (2,3)(3,4)183957=F4(2,3,4)(2,3,4) (2,4)(4,3)302757=F4(2,3,4) (2,4)(4,5)305383(2,4,5) (2,5)(5,4)254469=F4(2,4,5) (2,5)(5,6)257499(2,5,6) (2,6)(6,5)215778=F4(2,5,6)
7、(2,3)(3,5)185573(2,3,5) (2,5)(5,3)253459=F4(2,3,5) (2,3)(3,6)187189(2,3,6) (2,6)(6,3)213960=F4(2,3,6) (2,4)(4,6)3072102(2,4,6) (2,6)(6,4)215475=F4(2,4,6) (3,2)(2,4)196483(3,2,4) (3,4)(4,2)54449=F4(3,2,4) (3,2,5)(3,2)(2,5)197089(3,5)(5,2)103949=F4(3,2,5) (3,2)(2,6)197796(3,2,6) (3,6)(6,2)153449=F4(3,
8、2,6) (3,4)(4,5)55358(3,4,5) (3,5)(5,4)104454=F4(3,4,5) (3,4)(4,6)57277(3,4,6) (3,6)(6,4)155469=F4(3,4,6) (3,5)(5,6)107484(3,5,6) (3,6)(6,5)155772=F4(3,5,6) (4,2)(2,3)324173(4,2,3) (4,3)(3,2)43134=F4(4,2,3) (4,2)(2,5)3270102(4,2,5) (4,5)(5,2)83947=F4(4,2,5) (4,2)(2,6)3277109(4,2,6) (4,6)(6,2)163450=F
9、4(4,2,6) (4,3)(3,5)45559(4,3,5) (4,5)(5,3)83442=F4(4,3,5) (4,3)(3,6)47175(4,3,6) (4,6)(6,3)163955=F4(4,3,6) (4,5)(5,6)87482(4,5,6) (4,6)(6,5)165773=F4(4,5,6) (5,2)(2,3)274168(5,2,3) (5,3)(3,2)113142=F4(5,2,3) (5,2)(2,4)276491(5,2,4) (5,4)(4,2)104454=F4(5,2,4) (5,2)(2,6)2777104(5,2,6) (5,6)(6,2)18345
10、2=F4(5,2,6) (5,3)(3,4)113950(5,3,4) (5,4)(4,3)102737=F4(5,3,4) (5,3)(3,6)117182(5,3,6) (5,6)(6,3)183957=F4(5,3,6) (5,4)(4,6)107282(5,4,6) (5,6)(6,4)185472=F4(5,4,6) (6,2)(2,3)224163(6,2,3) (6,3)(3,2)163147=F4(6,2,3) (6,2)(2,4)226486(6,2,4) (6,4)(4,2)204464=F4(6,2,4) (6,2)(2,5)227092(6,2,5) (6,5)(5,2
11、)123951=F4(6,2,5) (6,3)(3,4)163955(6,3,4) (6,4)(4,3)202747=F4(6,3,4) (6,3)(3,5)165571(6,3,5) (6,5)(5,3)123446=F4(6,3,5)(6,4)(4,5)205373(6,4,5) (6,5)(5,4)124456=F4(6,4,5)（4）k=3 时，F3(i,S3) = minDi,j + F4(j,S4) i=2,3,4,5,6 X3=(i,S3)U3=(i,j)X4=(j,S4)V3=Di,jF4(j,S4)V3 + F4(j,S4) (2,3)(3,4,5)185472 (2,4)(
12、4,3,5)304272(2,3,4,5)(2,5)(5,3,4)253762=F3(2,3,4,5) (2,3)(3,4,6)186987 (2,4)(4,3,6)305585(2,3,4,6)(2,6)(6,3,4)214768=F3(2,3,4,6) (2,3)(3,5,6)187290 (2,5)(5,3,6)255782(2,3,5,6)(2,6)(6,3,5)214667=F3(2,3,5,6) (2,4)(4,5,6)3073103 (2,5)(5,4,6)257297(2,4,5,6)(2,6)(6,4,5)215677=F3(2,4,5,6) (3,2)(2,4,5)1969
13、88 (3,4)(4,2,5)54752=F3(3,2,4,5)(3,2,4,5)(3,5)(5,2,4)105464 (3,2)(2,4,6)197594 (3,4)(4,2,6)55055=F3(3,2,4,6)(3,2,4,6)(3,6)(6,2,4)156479 (3,2)(2,5,6)197897 (3,5)(5,2,6)105262=F3(3,2,5,6)(3,2,5,6)(3,6)(6,2,5)155166 (3,4)(4,5,6)57378 (3,5)(5,4,6)107282(3,4,5,6)(3,6)(6,4,5)155671=F3(3,4,5,6) (4,2)(2,3,5
14、)325991 (4,3)(3,2,5)44953(4,2,3,5)(4,5)(5,2,3)84250=F3(4,2,3,5) (4,2)(2,3,6)326092 (4,3)(3,2,6)44953=F3(4,2,3,6)(4,2,3,6)(4,6)(6,2,3)164763 (4,2)(2,5,6)3278110 (4,5)(5,2,6)85260=F3(4,2,5,6)(4,2,5,6)(4,6)(6,2,5)165167 (4,3)(3,5,6)47276 (4,5)(5,3,6)85765(4,3,5,6)(4,6)(6,3,5)164662=F3(4,3,5,6) (5,2,3,4)(5,2)(2,3,4)275784(5,3)(3,2,4)114960 (5,4)(4,2,3)103444=F3(5,2,3,4) (5,2)(2,3,6)276087 (5,3)(3,2,6)114960=F3(5,2,3,6)(5,2,3,6)(5,6)(6,2,3)184765 (5,2)(2,4,6)2775102 (5,4)(4,2,6)105060=F3(5,2,4,6)(5,
