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

【Abstract】 The Traveling Salesman Problem(TSP) is one of the typical NP-Complete hard problems in combinatorial optimization,which is easy to be described but hard to be solved.Its possible amounts of path increase exponentially with the amounts of city,so it is very difficult to solve.But to solve TSP quickly and effectively has important theoretical values and high practical application values.TSP is first introduced in this paper.Then the basic thoughts of six effective methods(simulated annealing algorithm,taboo search algorithm,Hopfield neural networks optimization algorithm,ant colony algorithm,genetic algorithms and hybrid optimization strategy) for solving TSP and their processes are discussed.At last,the advantages and disadvantages of the six main solving methods are respectively indicated,and the prospect for the future of solving TSP is provided.更多还原