TSP问题之动态规划法

TSP问题之动态规划法主讲人：葛忠雷提纲•什么是TSP问题•一般的解决办法——穷举法•动态的解决办法•什么是动态规划法•使用动态规划法的条件•动态规划法解决常见问题TSP问题TSP问题的描述：旅行家要旅行n个城市，要求经历各个城市且仅经历一次，然后回到出发城市，并要求所走的路程最短。0132366753726325TSP问题——穷举法解决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否TSP问题——动态规划假设找出的一条最短的回路：S0S1S2S3S0我们可以利用结论：“S1S2S3S0“必然是从S1到S0通过其它各点的一条最短路径。（如果不是，则会出现矛盾）S0S1S3S2Length(总回路)=Length(S0S1)+Length(S1S2S3S0)可以把问题简化：把求通过各点的一条最短的回路求解从某个（任意）确定点到回路中最后一个点的最短路径TSP问题——动态规划从上面的公式把总回路长度分解：•Length(回路)=Min{Length(01)+Length(1…0)，Length(02)+Length(2…0)，Length(03)+Length(3…0)}•规范化地表达上面的公式d(i，V)表示从i点经过点集Ｖ各点一次之后回到出发点的最短距离d(i，V‘)＝min{Cik+d(k,V－{k})}(k∈V')d(k，{})＝Cik(k≠i)其中，Ｃik表示ik的距离0132366753726325从城市0出发，经城市1、2、3然后回到城市0的最短路径长度是：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})=min{C12+d(2,{3}),C13+d(3,{2})}d(2,{1,3})=min{C21+d(1,{3}),C23+d(3,{1})}d(3,{1,2})=min{C31+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,{})573246325763)(ijcCC02+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思考：这个过程，让人联想到什么？理解原理之后，先手动地在表格中把结果写出来，结果如下：ji{}{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}0101586726951033121114从伪代码中可以看出，我们应当继续解决以下问题：•如何表示伪代码中集合Ｖ[j]呢?•如何产生这样的一个集合Ｖ[j]?TSP问题1．for(i=1;in;i++)//初始化第0列d[i][0]=c[i][0];2．for(j=1;j2n-1-1;j++)for(i=1;in;i++)//依次进行第i次迭代if(子集V[j]中不包含i)对V[j]中的每个元素k，计算d[i][j]=min(c[i][k]+d[k][j-1]);3．对V[2n-1-1]中的每一个元素k，计算d[0][2n-1-1]=min(c[0][k]+d[k][2n-1-2]);4．输出最短路径长度d[0][2n-1-1];１１１７１１０６１０１５０１１３１００４０１０２００１１００００二进制表示数字123７023６013５012４003３002２001１000０集合表示序号集合的表示模型动态规划法（一）动态规划法：定义：将每个子问题只求解一次，并将其解保存在一个表格中，当需要再次求解此子问题时，只是简单地通过查表获得该子问题的解，从而避免了大量的重复计算。特点：最优子结构、自底向递归、子问题相互重叠。动态规划法使用的条件：问题符合最优性原理动态规划法（二）最优性原理：对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段，每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据。无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。原理告诉我们，一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成。一般来说，如果所求解问题对于最优性原理成立，则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获取各阶段问题的递推关系式。动态规划法（三）动态规划法步骤（1）分段：将原问题分解为若干个相互重叠的子问题；（2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式；（3）求解：利用递推式自底向上计算，实现动态规划过程。动态规划法解决的常用问题（一）斐波那契数F(n)=0n=01n=1F(n-1)+F(n-2)n=2动态规划法解决的常用问题（二）多段图的最短路径问题2120345678949387684756866537动态规划法解决的常用问题（三）POJ1163数字三角形问题描述：在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径738810274445265动态规划法解决的常用问题（四）近似串匹配问题最长公共子序列问题０/１背包问题