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

作者：江贺; 胡燕; 李强; 于红

来源：软件学报, 2009, (09): 2344-2351.

• 旅行商问题
• NP-难解
• 脂肪
• 启发式 traveling salesman problem
• NP-hard
• fat
• heuristic algorithm

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

• 单位
  大连理工大学; 计算机科学国家重点实验室; 中国科学院软件研究所