Abstract:
The paper proposes a new algorithm named whole-priority algorithm to solve geometrical TSP, and the key thought of which is “adjusting while constructing”. A large number of experimental results indicate that the time complexity and space complexity of the algorithm are low, and its search-optimization ability is quite strong. The comprehensive performance of the algorithm exceeds some major algorithms and it is especially suitable for solving TSP on PC.
Key words:
TSP,
Whole-priority algorithm,
Approximate algorithm
摘要: 针对几何性质的TSP问题,提出了一种“整体优先”算法,算法的核心思想是边构造边调整。实验结果表明,该算法不仅时间复杂度和空间复杂度低,寻优能力也很强,其综合性能超过目前的一些主流算法,特别适合在微机上求解TSP问题。
关键词:
旅行商问题,
整体优先算法,
近似算法
CLC Number:
LIU Xin; LIU Renren; HOU Jingchuan. New Algorithm for Euclid TSP Problem[J]. Computer Engineering, 2007, 33(11): 64-66,6.
刘 新;刘任任;侯经川. 一种求解欧几里德TSP问题的新算法[J]. 计算机工程, 2007, 33(11): 64-66,6.