ISCAS OpenIR  > 基础软件与系统重点实验室
TSP问题的脂肪计算复杂性与启发式算法设计
江贺; 胡燕; 李强; 于红
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-难解问题具有一定的参考价值.
关键词旅行商问题 Np-难解 脂肪 启发式
部门归属大连理工大学软件学院;中国科学院软件研究所计算机科学国家重点实验室;
内容类型期刊论文
URI标识http://ir.iscas.ac.cn/handle/311060/8022
专题基础软件与系统重点实验室
推荐引用方式
GB/T 7714
江贺,胡燕,李强,等. TSP问题的脂肪计算复杂性与启发式算法设计[J]. 软件学报,2009(9):2344-2351.
APA 江贺,胡燕,李强,&于红.(2009).TSP问题的脂肪计算复杂性与启发式算法设计.软件学报(9),2344-2351.
MLA 江贺,et al."TSP问题的脂肪计算复杂性与启发式算法设计".软件学报 .9(2009):2344-2351.
条目包含的文件
条目无相关文件。
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[江贺]的文章
[胡燕]的文章
[李强]的文章
百度学术
百度学术中相似的文章
[江贺]的文章
[胡燕]的文章
[李强]的文章
必应学术
必应学术中相似的文章
[江贺]的文章
[胡燕]的文章
[李强]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。