| 求解TSP算法 |
| |
| 引用本文： | 周康,强小利,同小军,许进.求解TSP算法[J].计算机工程与应用,2007,43(29):43-47. |
| |
| 作者姓名： | 周康 强小利 同小军 许进 |
| |
| 作者单位： | 1. 华中科技大学,控制科学与工程系,武汉,430074;武汉工业学院,数理科学系,武汉,430023
2. 华中科技大学,控制科学与工程系,武汉,430074 |
| |
| 基金项目： | 国家自然科学基金
,
湖北省自然科学基金
,
浙江省自然科学基金
,
湖北省优秀中青年创新团队资助项目 |
| |
| 摘 要： | 首先提出旅行商问题(TSP),并将其转化为最短有向图哈密尔顿回路问题,然后介绍了三种类型的求解TSP的算法。第一种为传统算法,包括分支定界法、改良回路法、贪婪算法、MST算法、MM算法、插入法等;第二种为现代优化算法,包括模拟退火算法、人工免疫算法、遗传算法、蚁群算法、粒子群优化算法、禁忌搜索算法、Hopfield神经网络算法等;第三种为论文提出的DNA计算算法。并对这些算法的复杂度、误差范围以及优劣点进行了分析。
|
| 关 键 词： | TSP 传统算法 现代优化算法 DNA计算 |
| 文章编号： | 1002-8331（2007）29-0043-05 |
| 修稿时间： | 2007-06 |
Algorithm of TSP |
| |
| ZHOU Kang,QIANG Xiao-li,TONG Xiao-jun,XU Jin.Algorithm of TSP[J].Computer Engineering and Applications,2007,43(29):43-47. |
| |
| Authors: | ZHOU Kang QIANG Xiao-li TONG Xiao-jun XU Jin |
| |
| Affiliation: | 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 |
| |
| 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 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. |
| |
| Keywords: | traveling salesman problem tradition algorithm modern optimization algorithm DNA computing |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
