主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第11期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
江贺,胡燕,李强,于红.TSP问题的脂肪计算复杂性与启发式算法设计.软件学报,2009,20(9):2344-2351
TSP问题的脂肪计算复杂性与启发式算法设计
Fat Computational Complexity and Heuristic Design for the TSP
投稿时间:2008-04-08  修订日期:2008-07-02
DOI:
中文关键词:  旅行商问题  NP-难解  脂肪  启发式
英文关键词:traveling salesman problem  NP-hard  fat  heuristic algorithm
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60805024 (国家自然科学基金); the National Research Foundation for the Doctoral Program of the Ministry of Education of China under Grant No.20070141020 (国家教育部博士点基金)
作者单位
江贺 大连理工大学 软件学院,辽宁 大连 116621
中国科学院 软件研究所 计算机科学国家重点实验室,北京 100190 
胡燕 大连理工大学 软件学院,辽宁 大连 116621 
李强 大连理工大学 软件学院,辽宁 大连 116621 
于红 大连理工大学 软件学院,辽宁 大连 116621 
摘要点击次数: 3938
全文下载次数: 5145
中文摘要:
      旅行商问题(traveling salesman problem,简称TSP)是经典的NP-难解组合优化问题之一,求解它的高效启发式算法一直是计算机科学研究的热点.脂肪作为描述TSP结构特征的新工具,对启发式算法设计具有重要意义.目前,TSP问题的脂肪研究还处于初始阶段,缺乏理论分析结果及相关的启发式算法.首先分析了TSP问题的脂肪计算复杂性,通过构造偏移实例的技巧,证明了获取TSP的脂肪是NP-难解的,即在P?NP的假设下,不存在算法可以在多项式时间内获得完整脂肪.在此基础上,通过分析TSP问题局部最优解与脂肪的关系,给出了求解TSP问题的元启发式算法——动态候选集搜索(dynamic candidate set search,简称DCSS)算法.利用该算法,改进了目前求解TSP问题最好算法之一的LKH.TSPLIB典型实例的实验结果表明,改进后的算法在解的质量上有较为明显的提高.新的基于脂肪的启发式算法对于求解其他NP-难解问题具有一定的参考价值.
英文摘要:
      The traveling salesman problem (TSP) is one of the classic NP-Hard combinatorial optimization problems. Efficient heuristics for the TSP have been the focus in research of computer science at all times. As a new tool to describe the structure of the TSP, the fat is essential for heuristic algorithm design. Since research on the fat is still at the beginning stage, It still lacks theoretical results and related heuristic algorithms. In this paper Firstly, the fat computational complexity for the TSP is investigated. It’s proved that it is NP-Hard to obtain the fat of the TSP through construction of biased instances, i.e., there is no algorithm to get the full fat of the TSP in polynomial time on the assumption P?NP. Furthermore, a meta-heuristic——dynamic candidate set search (DCSS) was proposed by analysis of the