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

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