首页> 中文期刊> 《软件学报》 >TSP问题的脂肪计算复杂性与启发式算法设计

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

         

摘要

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

著录项

  • 来源
    《软件学报》 |2009年第9期|2344-2351|共8页
  • 作者

    江贺; 胡燕; 李强; 于红;

  • 作者单位

    大连理工大学;

    软件学院;

    辽宁;

    大连;

    116621;

    中国科学院;

    软件研究所;

    计算机科学国家重点实验室;

    北京;

    100190;

    大连理工大学;

    软件学院;

    辽宁;

    大连;

    116621;

    大连理工大学;

    软件学院;

    辽宁;

    大连;

    116621;

    大连理工大学;

    软件学院;

    辽宁;

    大连;

    116621;

  • 原文格式 PDF
  • 正文语种 chi
  • 中图分类 人工智能理论;
  • 关键词

    旅行商问题; NP-难解; 脂肪; 启发式;

相似文献

  • 中文文献
  • 外文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号