作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2007, Vol. 33 ›› Issue (11): 64-66,6. doi: 10.3969/j.issn.1000-3428.2007.11.024

• 软件技术与数据库 • 上一篇    下一篇

一种求解欧几里德TSP问题的新算法

刘 新1,刘任任1,侯经川2   

  1. (1. 湘潭大学信息工程学院,湘潭 411105;2. 湘潭大学管理学院,湘潭 411105)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-06-05 发布日期:2007-06-05

New Algorithm for Euclid TSP Problem

LIU Xin1, LIU Renren1, HOU Jingchuan2   

  1. (1. School of Information Engineering, Xiangtan University, Xiangtan 411105; 2. School of Management, Xiangtan University, Xiangtan 411105)
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-06-05 Published:2007-06-05

摘要: 针对几何性质的TSP问题,提出了一种“整体优先”算法,算法的核心思想是边构造边调整。实验结果表明,该算法不仅时间复杂度和空间复杂度低,寻优能力也很强,其综合性能超过目前的一些主流算法,特别适合在微机上求解TSP问题。

关键词: 旅行商问题, 整体优先算法, 近似算法

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

中图分类号: