旅行商问题是“易于描述,难于求解”的典型问题。旅行商问题的高效解法是否存在?这个问题涉及可行计算的界限,触及复杂性理论的核心。旅行商问题在基因组测序、计算机处理器设计、行星寻找等许多领域也有着广泛的应用。由于旅行商所具有的重要的理论意义和实践意义,使它成为了组合优化问题中被研究得最多的问题之一。它驱动着应用数学领域以及运筹学与数学规划的发展方向,对新发现起到了有目共睹的带动作用。回顾旅行商问题的研究历史,人们最先研究的便是精确算法,但随着人们对NP问题认识的加深,试图使用精确算法求解旅行商问题的研究已经难觅踪迹,多年来普遍研究的是各种近似方法。与之相对应,目前大多数本领域的知名权威倾向于认为,NP不等于P,即使权威们对此拿不出任何有力的证据,但此看法似乎被大多数人默认。然而历史上并不缺乏打破权威思想禁锢,发现真理的故事。在旅行商问题的精确算法中,已知的运行时间界限是由Held和Karp的动态规划法给出的。Held-Karp解法能在正比于n22n的时间内解决任何一道n座城市的TSP题目。本文基于对插入算法的研究,重新设计了不同于Held-Karp解法的新动态规划算法。本文所完成的主要研究工作有:(1)根据凸包规则优化改进了旅行商问题的回溯算法,提高了回溯算法有效解题的城市规模上限,该算法在可接受的时间内成功解决了中国旅行商问题;(2)深入研究了旅行商问题的插入算法,从实验结果分析提出了简单插入最优性猜想和同型插座猜想,同时设计了实验进行验证;(3)依据简单插入最优性猜想提出了基于简单插入子集的动态规划算法;(4)依据同型插座猜想猜想提出最优插入子集的概念,并据此设计出新动态规划法,同时对新动态规划法进行了性能分析和复杂度计算。新动态规划法有着更简单的结构,同时也达到了 n22n的运行时间界限;(5)结合实例详细描述了新算法的执行过程,编写程序实现算法,实验结果证明了新算法的有效性。任何算法都有其优势也会有缺陷,优化算法设计是一个永恒的研究课题。本文所提出的方法为求解旅行商问题提供了新的思路,对于认识、分析众多复杂问题具有一定的启示,对促进组合优化问题的研究有着积极的作用。