摘要
首先提出旅行商问题(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.
出处
《计算机工程与应用》
CSCD
北大核心
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
传统算法
现代优化算法
DNA计算
traveling salesman problem
tradition algorithm
modern optimization algorithm
DNA computing
