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

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

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