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

【Abstract】 This paper is enlightened by the surface tension in the process of water-flow, Firstly, it constructs a protruding polygon which passes through some points, and adds other points to the loop according to multifarious heuristic information one by one. The results show the algorithm can approach optimal answer well in a minute. Additionally , we obtain two optimal loop theorem of TSP under certain conditions, and prove them to provide the theoretical base of the algorithm.更多还原