计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (29): 43-47.

• 学术探讨 • 上一篇    下一篇

求解TSP算法

周 康1,2,强小利1,同小军1,2,许 进1   

  1. 1.华中科技大学 控制科学与工程系,武汉 430074
    2.武汉工业学院 数理科学系,武汉 430023
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-10-11 发布日期:2007-10-11
  • 通讯作者: 周 康

Algorithm of TSP

ZHOU Kang1,2,QIANG Xiao-li1,TONG Xiao-jun1,2,XU Jin1   

  1. 1.Department of Control Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074,China
    2.Department of Mathematics and Physics,Wuhan Polytechnic University,Wuhan 430023,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-10-11 Published:2007-10-11
  • Contact: ZHOU Kang

摘要: 首先提出旅行商问题(TSP),并将其转化为最短有向图哈密尔顿回路问题,然后介绍了三种类型的求解TSP的算法。第一种为传统算法,包括分支定界法、改良回路法、贪婪算法、MST算法、MM算法、插入法等;第二种为现代优化算法,包括模拟退火算法、人工免疫算法、遗传算法、蚁群算法、粒子群优化算法、禁忌搜索算法、Hopfield神经网络算法等;第三种为论文提出的DNA计算算法。并对这些算法的复杂度、误差范围以及优劣点进行了分析。

关键词: TSP, 传统算法, 现代优化算法, DNA计算

Abstract: TSP is brought forward and is transformed into shortest closed Hamilton loop of directed graph problem.Then three kind of algorithms of TSP is indroduced.One is tradition algorithm,which consists branch and bound method,improving loop method,cupidity algorithm,MST algorithm,MM algorithm,insertion method.Another is modern optimization algorithm which consists simulated annealing algorithm,artificial immune algorithm,genetic algorithm,ant colony algorithm,particle swarm optimization,Tabu Search,Hopfield neural network.The third is algorithm of DNA computing which is designed by authors.Complexity and error range of the DNA algorithm are discussed,and the advantage and shortcoming points of algorithms are analyzed.

Key words: traveling salesman problem, tradition algorithm, modern optimization algorithm, DNA computing