论文部分内容阅读
<正> 1.思想来源旅行商问题(TSP)可以简单表述如下:给定一组N个城市和它们之间的两两距离,找出一个闭合的旅程,使得每个城市刚好经过一次且总的旅程距离最短。旅行商问题已经被证实是一个NP难解问题。虽然欧氏平面上的TSP有PTAS,但运算时间和精度呈指数函数关系,所以找一个快速的近似算法仍然具有很大的意义。近年来提出的逼近最优解的算法如遗传算法、模拟退火算法、神经网络算法本质上都是进行随机搜索,本文是用确定性的启发式算法求解TSP。