TSP问题之动态规划法PPT课件.ppt

TSPTSP问题之动态规划法1.提纲什么是TSP问题一般的解决办法穷举法动态的解决办法什么是动态规划法使用动态规划法的条件动态规划法解决常见问题2.TSP问题TSP问题的描述：旅行家要旅行n个城市，要求经历各个城市且仅经历一次，然后回到出发城市，并要求所走的路程最短。013236 67537263253.TSP问题穷举法解决abdc235187序号路径路径长度是否最短a-b-c-d-a18否a-b-d-c-a11是ac-b-d-a23否a-c-d-b-a11是a-d-b-c-a23否a-d-c-b-a18否4.TSP问题动态规划假设找出的一条最短的回路：S0S1S2 S3S0我们可以利用结论：S1S2 S3S0“必然是从S1 到S0通过其它各点的一条最短路径。（如果不是，则会出现矛盾）S0S1S3S2Length(总回路)=Length(S0S1)+Length(S1 S2 S3S0)可以把问题简化：把求通过各点的一条最短的回路 求解从某个（任意）确定点到回路中最后一个点的最短路径5.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)(k V)d(k，)Cik(ki)其中，ik表示ik的距离 0132366753 7243256.从城市0出发，经城市1、2、3然后回到城市0的最短路径长度是：d(0,1,2,3)=minC01+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(3,2)=C32+d(2,)d(1,3)=C13+d(3,)d(2,1)=C21+d(1,)d(3,1)=C31+d(1,)7.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,)C21+d(1,)C30C20C10思考：这个过程，让人联想到什么？8.理解原理之后，先手动地在表格中把结果写出来，结果如下：ji1231,21,32,31,2,301015867269510331211149.从伪代码中可以看出，我们应当继续解决以下问题：如何表示伪代码中集合 j 呢?如何产生这样的一个集合 j?TSP问题1for(i=1;in;i+)/初始化第0列di0=ci0;2for(j=1;j2n-1-1;j+)for(i=1;i=215.动态规划法解决的常用问题（二）l多段图的最短路径问题212034567894938768475686653716.动态规划法解决的常用问题（三）lPOJ 1163 数字三角形问题描述：在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 17.动态规划法解决的常用问题（四）l近似串匹配问题l最长公共子序列问题l/背包问题18.