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

摘要

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