【摘要】 针对多阶段决策过程求解旅行商问题中离散确定性决策模型单一的问题，提出一种基于最优插入子集的动态规划法。通过研究旅行商问题的插入算法，提出简单插入最优性猜想和同型插座猜想并应用不完全归纳法进行测试。依据同型插座猜想的推论，引入最优插入子集的概念，重新设计了不同于Held-Karp解法的新算法。实验结果表明，该算法在不同数据集上均能求得最优解，并达到已知的运行时间界限。更多还原

【Abstract】 Aiming at the problem of single discrete deterministic decision model in multi-stage decision process for traveling salesman problem, we propose a new dynamic programming method based on the optimal insertion subset. By studying the insertion algorithm of TSP, the simple insertion optimality conjecture and the same type socket conjecture were proposed and tested by incomplete induction method. According to the inference of the same type socket conjecture, the concept of the optimal insertion subset was proposed, and a new dynamic programming algorithm different from the Held-Karp method was redesigned. The experimental results show that this algorithm can get the optimal solution on different data sets and reach the known running time limit.更多还原