求解TSP问题的一种启发式算法

• 作者: 孙宪丽 李颖 王敏
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 旅行商问题 启发式算法 最小生成树
• 年，卷（期）: 2010,（10）
• 页码范围: 70-73,77
• 分类号: TP301.6
• 字数: 2265字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2010.10.018

摘要

TSP问题模型应用广泛,其求解策略的研究具有重要的理论和实践意义.根据TSP问题的特点,借鉴无向完全图上最小生成树的生成过程,设计了一种启发式算法对TSP问题进行求解.该算法的基本思想是以无向完全图上不同最小生成树为基础,采用启发式的方法构造不同闭合回路,最后取最短闭合回路作为最优解.文中采用C语言编程,同时分析了算法的性能和时间复杂度,并进行了大量仿真计算.结果表明设计的算法能够有效求得TSP问题的优化解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王敏	沈阳工程学院基础部	12	46	4.0	6.0
2	李颖	沈阳工程学院基础部	14	46	4.0	6.0
3	孙宪丽	沈阳工程学院信息系	13	57	4.0	7.0