中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 计算机科学国家重点实验室  > 期刊论文
题名:
TSP问题的脂肪计算复杂性与启发式算法设计
作者: 江贺 ; 胡燕 ; 李强 ; 于红
关键词: 旅行商问题 ; NP-难解 ; 脂肪 ; 启发式
刊名: 软件学报
发表日期: 2009
期: 9, 页:2344-2351
部门归属: 大连理工大学软件学院;中国科学院软件研究所计算机科学国家重点实验室;
摘要: 旅行商问题(traveling salesman problem,简称TSP)是经典的NP-难解组合优化问题之一,求解它的高效启发式算法一直是计算机科学研究的热点.脂肪作为描述TSP结构特征的新工具,对启发式算法设计具有重要意义.目前,TSP问题的脂肪研究还处于初始阶段,缺乏理论分析结果及相关的启发式算法.首先分析了TSP问题的脂肪计算复杂性,通过构造偏移实例的技巧,证明了获取TSP的脂肪是NP-难解的,即在P≠NP的假设下,不存在算法可以在多项式时间内获得完整脂肪.在此基础上,通过分析TSP问题局部最优解与脂肪的关系,给出了求解TSP问题的元启发式算法——动态候选集搜索(dynamic candidate set search,简称DCSS)算法.利用该算法,改进了目前求解TSP问题最好算法之一的LKH.TSPLIB典型实例的实验结果表明,改进后的算法在解的质量上有较为明显的提高.新的基于脂肪的启发式算法对于求解其他NP-难解问题具有一定的参考价值.
内容类型: 期刊论文
URI标识: http://ir.iscas.ac.cn/handle/311060/8022
Appears in Collections:计算机科学国家重点实验室 _期刊论文

Files in This Item:

There are no files associated with this item.


Recommended Citation:
江贺,胡燕,李强,等. TSP问题的脂肪计算复杂性与启发式算法设计[J]. 软件学报,2009-01-01(9):2344-2351.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[江贺]'s Articles
[胡燕]'s Articles
[李强]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[江贺]‘s Articles
[胡燕]‘s Articles
[李强]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace