TSP问题之动态规划法

1、旅行商问题的动态规划方法，概述，旅行商问题的一般解决方案，穷举方法，动态解决方案，动态规划方法，有条件的动态规划方法，解决共同的问题，旅行商问题，旅行商问题描述：旅行者需要旅行到n个城市，他们只需要通过每个城市一次，然后返回到出发城市，并要求最短的距离。用穷举法求解旅行商问题，旅行商问题是动态规划的，并假设找到一个最短的循环：S0S1S2 S3S0。我们可以得出这样的结论：“S1S2 S3S0”一定是从S1到S0通过其他点的最短路径。(如果没有，就会有矛盾)，Length(总循环)=Length(S0S1) Length(S1 S2 S3S0)，这样可以简化问题：为了求解从某个(任意)点到循环

2、中最后一点的最短路径，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的距离，从城市0到城市1，2，3然后回到城市0的最短路径长度为：d (0，1，3)，C02 d(2，1，3)，C03 d(3，1，2)这是最终决定。 其中必须基于d(1

3、，2，3)，d(2，1，3)和d(3，1，2)的计算结果，而：D (1，1，2) 3)=最小c21d (1，3)，c23d (3，1) d (3，1，2)=最小c31d (1，2)，c32d (2，1)继续写：d (1，2)=c12 d (2，2) d (2，2) 3)=C13D (3)，d (2，1)=C23D 思考：这个过程让人想起什么？理解了原理后，首先手工将结果写在表格中。结果如下：从伪代码来看，我们应该继续解决以下问题：如何在伪代码中表达集合j？如何生成这样的集合j？集合表示模型，动态规划方法(一)，动态规划方法：定义：每个子问题只求解一次，并将其解保存在表中。当需要再次求解这个子问

4、题时，这个子问题的解只需查表就可以得到，从而避免了大量的重复计算。特点：最优子结构，自底向上递归和重叠子问题。使用动态规划方法的条件：问题符合最优性原则，而动态规划方法(2)，最优性原则：对于一个有n个输入的优化问题，其求解过程通常可以分为几个阶段，每个阶段的决策只取决于前一阶段的状态，而决策所采取的行动使状态发生变化，这就成为下一阶段决策的基础。不管过程的初始状态和决策，其余的决策必须形成相对于由初始决策产生的状态的最优决策序列。该原理告诉我们，最优问题的任何实例的最优解都是由该实例的子实例的最优解组成的。一般来说，如果最优化原理成立，它表明通过动态规划解决问题是可能的。解决问题的关键在于获得各阶段的递推关系。动态规划方法(3)，动态规划方法步骤(1)分段：将原问题分解成几个重叠的子问题；(2)分析：分析问题是否满足最优性原则，找出动态规划函数的递推公式；(3)解决方案：采用递归自底向上计算实现动态规划过程。动态规划法解决的常见问题(1)、斐波那契数、动态规划法解决的常见问题(2)、多段图的最短路径问题、动态规划法解决的常见问题(3)、POJ 1163数字三角形问题描述：在上述数字三角形中从上到下寻找一条路径，使通过该路径的数字之和最大化。道路上的每一步只能走到左下方或右下方。我们只需要找到这个最大和，不给出具