基于最优插入子集的动态规划算法求解旅行商问题  

DYNAMIC PROGRAMMING ALGORITHM BASED ON OPTIMAL INSERTION SUBSET FOR TRAVELLING SALESMAN PROBLEM

作　　者：但开 段隆振[1] Dan Kai;Duan Longzhen(School of Information Engineering,Nanchang University,Nanchang 330031,Jiangxi,China)

机构地区：[1]南昌大学信息工程学院,江西南昌330031

出　　处：《计算机应用与软件》2022年第12期260-265,297,共7页Computer Applications and Software

基　　金：国家自然科学基金项目(61070139,81460769)。

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

关 键 词：旅行商问题 动态规划 组合优化 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]