首页 | 本学科首页   官方微博 | 高级检索  
     

TSP问题的脂肪计算复杂性与启发式算法设计
引用本文:江贺,胡燕,李强,于红.TSP问题的脂肪计算复杂性与启发式算法设计[J].软件学报,2009,20(9):2344-2351.
作者姓名:江贺  胡燕  李强  于红
作者单位:1. 大连理工大学,软件学院,辽宁,大连,116621;中国科学院,软件研究所,计算机科学国家重点实验室,北京,100190
2. 大连理工大学,软件学院,辽宁,大连,116621
基金项目:国家自然科学基金,教育部高等学校博士学科点专项科研基金
摘    要:旅行商问题(traveling salesman problem,简称TSP)是经典的NP-难解组合优化问题之一,求解它的高效启发式算法一直是计算机科学研究的热点.脂肪作为描述TSP结构特征的新工具,对启发式算法设计具有重要意义.目前,TSP问题的脂肪研究还处于初始阶段,缺乏理论分析结果及相关的启发式算法.首先分析了TSP问题的脂肪计算复杂性,通过构造偏移实例的技巧,证明了获取TSP的脂肪是NP-难解的,即在P(NP的假设下,不存在算法可以在多项式时间内获得完整脂肪.在此基础上,通过分析TSP问题局部最优解与脂肪的关系,给出了求解TSP问题的元启发式算法--动态候选集搜索(dynamic candidate set search,简称DCSS)算法.利用该算法,改进了目前求解TSP问题最好算法之一的LKH.TSPLIB典型实例的实验结果表明,改进后的算法在解的质量上有较为明显的提高.新的基于脂肪的启发式算法对于求解其他NP-难解问题具有一定的参考价值.

关 键 词:旅行商问题  NP-难解  脂肪  启发式
收稿时间:4/8/2008 12:00:00 AM
修稿时间:7/2/2008 12:00:00 AM

Fat Computational Complexity and Heuristic Design for the TSP
JIANG He,HU Yan,LI Qiang and YU Hong.Fat Computational Complexity and Heuristic Design for the TSP[J].Journal of Software,2009,20(9):2344-2351.
Authors:JIANG He  HU Yan  LI Qiang and YU Hong
Abstract:
Keywords:traveling salesman problem  NP-hard  fat  heuristic algorithm
本文献已被 万方数据 等数据库收录!
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号