TSP问题的脂肪计算复杂性与启发式算法设计  

Fat Computational Complexity and Heuristic Design for the TSP

作　　者：江贺[1,2] 胡燕[1] 李强[1] 于红[1] 

机构地区：[1]大连理工大学软件学院,辽宁大连116621 [2]中国科学院软件研究所计算机科学国家重点实验室,北京100190

出　　处：《软件学报》2009年第9期2344-2351,共8页Journal of Software

基　　金：国家自然科学基金No.60805024;国家教育部博士点基金No.20070141020~~

摘　　要：旅行商问题(traveling salesman problem,简称TSP)是经典的NP-难解组合优化问题之一,求解它的高效启发式算法一直是计算机科学研究的热点.脂肪作为描述TSP结构特征的新工具,对启发式算法设计具有重要意义.目前,TSP问题的脂肪研究还处于初始阶段,缺乏理论分析结果及相关的启发式算法.首先分析了TSP问题的脂肪计算复杂性,通过构造偏移实例的技巧,证明了获取TSP的脂肪是NP-难解的,即在P≠NP的假设下,不存在算法可以在多项式时间内获得完整脂肪.在此基础上,通过分析TSP问题局部最优解与脂肪的关系,给出了求解TSP问题的元启发式算法——动态候选集搜索(dynamic candidate set search,简称DCSS)算法.利用该算法,改进了目前求解TSP问题最好算法之一的LKH.TSPLIB典型实例的实验结果表明,改进后的算法在解的质量上有较为明显的提高.新的基于脂肪的启发式算法对于求解其他NP-难解问题具有一定的参考价值.The traveling salesman problem （TSP） is one of the classic NP-Hard combinatorial optimization problems. Efficient heuristics for the TSP have been the focus in research of computer science at all times. As a new tool to describe the structure of the TSP, the fat is essential for heuristic algorithm design. Since research on the fat is still at the beginning stage, It still lacks theoretical results and related heuristic algorithms. In this paper Firstly, the fat computational complexity for the TSP is investigated. It＇s proved that it is NP-Hard to obtain the fat of the TSP through construction of biased instances, i.e., there is no algorithm to get the full fat of the TSP in polynomial time on the assumption P^NP. Furthermore, a meta-heuristic- - dynamic candidate set search （DCSS） was proposed by analysis of the relationship between local optimal solutions and the fat. And the DCSS was applied to the LKH, one of the best existing algorithms for the TSP to improve it. Extensively wide experimental results on typical instances from the benchmark--TSPLIB indicate that the improved algorithm has a better performance than the LKH in terms of solution quality. This new fat-based heuristic shows a new way for other NP-hard problems.

关 键 词：旅行商问题 NP-难解 脂肪 启发式 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]