摘要： 提出了一种新的基于最大相似性的TSP问题求解算法。该算法在最近邻算法(Nearest-Neighbor Algorithm)的基础上作了改进,将最短路径问题转换为最大相似性问题,即将问题由选取城市 ij+1= arg min{djk:k ∈V\ {i1, i2,…,ij}} 转换为选取城市 ij+1= arg min{wjk:k ∈V\ {i1, i2,…,ij}} ,wjk 为城市i与城市j之间的相似系数。实验结果表明,该算法简明且具有较好的有效性。

关键词: TSP问题, 最近邻算法, 最大相似性算法

Abstract: This paper proposes a new algorithm for TSP—— similarity-based algorithm. The proposed algorithm is on the basis of nearest-neighbor algorithm, which selects a city according to the following formula: ij+1= arg min{djk: k ∈V \{i1, i2,…,ij}}. In order to improve the basic NN algorithm, the similarity-based algorithm decides the city by a different method: ij+1= arg min{wjk: k ∈V \{i1, i2,…,ij}} ,wjk represents the similarity between city i and city j. Experiment results show that the algorithm is practical.

中图分类号: 

• TP301.6