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

• 作者: 于红 李强 江贺 胡燕
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 旅行商问题 NP-难解 脂肪 启发式
• 年，卷（期）: 2009,（9）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 2344-2351
• 页数: 8页
• 分类号: TP18
• 字数: 7068字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2009.03418

摘要

旅行商问题(traveling salesman problem,简称TSP)是经典的NP-难解组合优化问题之一,求解它的高效启发式算法一直是计算机科学研究的热点.脂肪作为描述TSP结构特征的新工具,对启发式算法设计具有重要意义.目前,TSP问题的脂肪研究还处于初始阶段,缺乏理论分析结果及相关的启发式算法.首先分析了TSP问题的脂肪计算复杂性,通过构造偏移实例的技巧,证明了获取TSP的脂肪是NP-难解的,即在P(NP的假设下,不存在算法可以在多项式时间内获得完整脂肪.在此基础上,通过分析TSP问题局部最优解与脂肪的关系,给出了求解TSP问题的元启发式算法--动态候选集搜索(dynamic candidate set search,简称DCSS)算法.利用该算法,改进了目前求解TSP问题最好算法之一的LKH.TSPLIB典型实例的实验结果表明,改进后的算法在解的质量上有较为明显的提高.新的基于脂肪的启发式算法对于求解其他NP-难解问题具有一定的参考价值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	于红	大连理工大学软件学院	21	125	6.0	10.0
2	胡燕	大连理工大学软件学院	8	59	4.0	7.0
3	江贺	大连理工大学软件学院	47	513	12.0	21.0
5	李强	大连理工大学软件学院	29	239	9.0	15.0