求解TSP算法  

Algorithm of TSP

作　　者：周康[1] 强小利[1] 同小军[1] 许进[1] 

机构地区：[1]华中科技大学控制科学与工程系

出　　处：《计算机工程与应用》2007年第29期43-47,85,共6页Computer Engineering and Applications

基　　金：国家自然科学基金( the National Natural Science Foundation of China under Grant No.60373089) ;湖北省自然科学基金( the Natural Science Foundation of Hubei Province of China under Grant No.2005ABA233);浙江省自然科学基金( the Natural Science Foundation of Zhejiang Province of China under Grant No.ZJNSF- Y105654);湖北省优秀中青年科技创新团队计划

摘　　要：首先提出旅行商问题(TSP),并将其转化为最短有向图哈密尔顿回路问题,然后介绍了三种类型的求解TSP的算法。第一种为传统算法,包括分支定界法、改良回路法、贪婪算法、MST算法、MM算法、插入法等;第二种为现代优化算法,包括模拟退火算法、人工免疫算法、遗传算法、蚁群算法、粒子群优化算法、禁忌搜索算法、Hopfield神经网络算法等;第三种为论文提出的DNA计算算法。并对这些算法的复杂度、误差范围以及优劣点进行了分析。TSP is brought forward and is transformed into shortest closed Hamilton loop of directed graph problem.Then three kind of algorithms of TSP is indreduced.One is tradition algorithm,which consists branch and bound method,improving loop method,cupidity algorithm,MST algorithm,MM algorithm,insertion method.Another is modem 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.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]