旅行商问题(TSP)的几种求解方法

被引：33

作者：

田贵超

黎明

韦雪洁

机构：

[1] 南昌航空工业学院测试技术与控制工程系

来源：

计算机仿真 | 2006年 / 08期

关键词：

旅行商问题; 组合优化; 路径; 展望;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

旅行商问题(TSP)是组合优化领域里的一个典型的、易于描述却难以处理的NP完全难题,其可能的路径数目与城市数目是呈指数型增长的,求解非常困难。而快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。该文首先介绍了什么是TSP,接着论述了六种目前针对TSP比较有效的解决方法(模拟退火算法、禁忌搜索算法、Hopfie ld神经网络优化算法、蚁群算法、遗传算法和混合优化策略)的基本思想,并且简单阐述了它们的求解过程,最后分别指出了各自的优缺点并对解决TSP的前景提出了展望。

引用

页码：153 / 157

页数：5

共 7 条

[1]

遗传算法[M]. 西安交通大学出版社 , 王小平, 2002

[2]

智能优化算法及其应用[M]. 清华大学出版社 , 王凌著, 2001

[3]

遗传算法与工程设计[M]. 科学出版社 , (日)玄光男, 2000

[4]

人工神经网络与模拟进化计算[M]. 清华大学出版社 , 阎平凡, 2000

[5]

遗传算法原理及应用[M]. 国防工业出版社 , 周明, 1999

[6]

遗传算法及其应用[M]. 人民邮电出版社 , 陈国良等编著, 1996

[7]

G enetic A lgorithm s for the Sa lesm anProb lem .2 J J G refenstettee. Proceed ings of the F irst Internationa lCon ference on G enetic A lgorithm s . 1985

← 1 →