TSP问题之动态划法.ppt

TSP问题之动态规划法 提纲 什么是TSP问题 一般的解决办法——穷举法 动态的解决办法 什么是动态规划法 使用动态规划法的条件 动态规划法解决常见问题 动态规划法（一） 动态规划法： 定义：将每个子问题只求解一次，并将其解保存在一个表格中，当需要再次求解此子问题时，只是简单地通过查表获得该子问题的解，从而避免了大量的重复计算。 特点：最优子结构、自底向递归、子问题相互重叠。 动态规划法使用的条件：问题符合最优性原理 动态规划法（二） 最优性原理： 对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段，每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据。 无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。 原理告诉我们，一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成。 一般来说，如果所求解问题对于最优性原理成立，则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获取各阶段问题的递推关系式。 动态规划法（三） 动态规划法步骤 （1）分段：将原问题分解为若干个相互重叠的子问题； （2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式； （3）求解：利用递推式自底向上计算，实现动态规划过程。 动态规划法解决的常用问题（一） 斐波那契数 动态规划法解决的常用问题（二） 多段图的最短路径问题 动态规划法解决的常用问题（三） POJ 1163 数字三角形 问题描述：在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径 动态规划法解决的常用问题（四） 近似串匹配问题 最长公共子序列问题 ０/１背包问题 * 主讲人：葛忠雷 TSP问题 TSP问题的描述： 旅行家要旅行n个城市，要求经历各个城市且仅经历一次，然后回到出发城市，并要求所走的路程最短。 0 1 3 2 3 6 6 7 5 3 7 2 6 3 2 5 TSP问题——穷举法解决 a b d c 2 3 5 1 8 7 否 18 a-d-c-b-a ６ 否 23 a-d-b-c-a ５ 是 11 a-c-d-b-a ４ 否 23 ac-b-d-a ３ 是 11 a-b-d-c-a ２ 否 18 a-b-c-d-a １ 是否最短 路径长度 路径 序号 TSP问题——动态规划 假设找出的一条最短的回路：S0?S1?S2 ? S3?S0 我们可以利用结论： “S1?S2 ? S3?S0 “必然是从S1 到S0通过其它各点的一条最短路径。（如果不是，则会出现矛盾） S0 S1 S3 S2 Length(总回路) = 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的距离 0 1 3 2 3 6 6 7 5 3 7 2 6 3 2 5 从城市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})