TSP问题之动态规划法

1、2021/3/111 TSPTSP问题之动态规划法问题之动态规划法 2021/3/112 提纲提纲 什么是TSP问题 一般的解决办法穷举法 动态的解决办法 什么是动态规划法 使用动态规划法的条件 动态规划法解决常见问题 2021/3/113 TSP问题问题 TSP问题的描述： 旅行家要旅行n个城市，要求经历各个城市且 仅经历一次，然后回到出发城市，并要求所走的路 程最短。 01 3 2 3 6 6 7 5 3 7 2 6 3 2 5 2021/3/114 TSP问题问题穷举法解决穷举法解决 ab dc 2 3 5 1 8 7 序号路径路径长度是否最短 a-b-c-d-a18 否 a-b-d-c

2、-a11是是 ac-b-d-a23 否 a-c-d-b-a11是是 a-d-b-c-a23 否 a-d-c-b-a18 否 2021/3/115 TSP问题问题动态规划动态规划 假设找出的一条最短的回路：S0S1S2 S3S0 我们可以利用结论： “S1S2 S3S0 “必然是从S1 到S0 通过其它各点的一条最短路径。（如果不是，则会出现矛盾） S0S1 S3 S2 Length(总回路总回路) = Length(S0S1) + Length(S1 S2 S3S0) 可以把问题简化： 把求通过各点的一条最短的回路 求解从某个（任意）确定点到回路中 最后一个点的最短路径 2021/3/116

3、TSP问题问题动态规划动态规划 从上面的公式把总回路长度分解： Length(回路) = Min Length(01) + Length(10)， Length(02) + Length(20)， Length(03) + Length(30) 规范化地表达上面的公式 d(i，V) 表示从i点经过点集各点一次之后回到出发点的最短距离 d(i，V) min Cik+d(k,Vk) (kV) d(k， ) Cik (ki) 其中，其中，ik表示表示ik的距离的距离 01 3 2 3 66 7 5 3 7 2 4 3 2 5 2021/3/117 从城市0出发，经城市1、2、3然后回到城市0的最短路

4、径长度是： d(0, 1, 2, 3)=min C01+ d(1, 2, 3), C02+ d(2, 1, 3), C03+ d(3, 1, 2) 这是最后一个阶段的决策，它必须依据d(1, 2, 3)、 d(2, 1, 3)和d(3, 1, 2)的计算结果，而： d(1, 2, 3)=minC12+d(2, 3), C13+ d(3, 2) d(2, 1, 3)=minC21+d(1, 3), C23+ d(3, 1) d(3, 1, 2)=minC31+d(1, 2), C32+ d(2, 1) 继续写下去： d(1, 2)= C12+d(2, ) d(2, 3)=C23+d(3, ) d

5、(3, 2)= C32+d(2, ) d(1, 3)= C13+d(3, ) d(2, 1)=C21+d(1, ) d(3, 1)= C31+d(1, ) 573 246 325 763 )( ij cC 2021/3/118 C02+ d(2, 1, 3)C01+ d(1, 2, 3)C03+ d(3, 1, 2) d(0, 1, 2, 3) C12+d(2, 3) C13+ d(3, 2) C21+d(1, 3) C23+ d(3, 1) C31+d(1, 2) C32+ d(2, 1) C23+d(3, )C32+d(2, )C13+d(3, ) C31+d(1, )C12+d(2, )

6、 C21+d(1, ) C30C20C10 思考：这个过程，思考：这个过程， 让人联想到什么？让人联想到什么？ 2021/3/119 理解原理之后，先手动地在表格中把结果写出来，结果如下：理解原理之后，先手动地在表格中把结果写出来，结果如下： j i 1231, 21, 32, 3 1, 2, 3 0 10 15 86 7 269 5 10 331211 14 2021/3/1110 从伪代码中可以看出，我们应当继续解决以下问题： 如何表示伪代码中集合 j 呢? 如何产生这样的一个集合 j ? TSP问题问题 1for (i=1; in; i+) /初始化第初始化第0列列 di0=ci0; 2for (j=1; j2n-1- -1; j+) for (i=1; i=2 2021/3/1116 动态规划法解决的常用问题（二）动态规划法解决的常用问题（二） l 多段图的最短路径问题 2 1 20 3 4 5 6 7 8 9 4 9 3 8 7 6 8 4 7 5 6 8 6 6 5 3 7 2021/3/1117 动态规划法解决的常用问题（三）动态规划法解决的常用问题（三） l POJ 1163 数字三角形 问题描述：在上面的数字三角形中寻找一条从顶部到底边的 路径，使得路径上所经过的数字之和最大。路径上的每一步都只能 往左下或右下走。只需要求出这个最大和即可，不必