| 求旅行商问题近似解的碰撞算法 |
| |
| 引用本文： | 邱伟星,王舒榕,程栋材,邢晓伟,陈春玲,姜冬健.求旅行商问题近似解的碰撞算法[J].计算机工程,2011,37(10):284-286. |
| |
| 作者姓名： | 邱伟星 王舒榕 程栋材 邢晓伟 陈春玲 姜冬健 |
| |
| 作者单位： | 南京邮电大学计算机学院,南京,210003 |
| |
| 基金项目： | 邱伟星(1952－)，男，副教授，主研方向：数论，组合优化，密码学；王舒榕，硕士研究生；程栋材，学士；邢晓伟，硕士；陈春玲，副教授；姜冬健，学士 |
| |
| 摘 要： | 提出通过寻找精确解的边获得旅行商问题(TSP)近似解的思想，并以该思想为指导，设计一种新的碰撞算法。对国际通用的TSPLIB中不同城市规模的数据进行测试表明，该算法可以得到与目前已知最优解或相同或相近的结果。该算法不仅可以计算小规模的TSP，而且同样适用较大规模的TSP。
|
| 关 键 词： | 旅行商问题 三角剖分 组合优化 碰撞算法 |
Collision Algorithm for Approximate Solution of Traveling Salesman Problem |
| |
| QIU Wei-xing,WANG Shu-rong,CHENG Dong-cai,XING Xiao-wei,CHEN Chun-ling,JIANG Dong jian.Collision Algorithm for Approximate Solution of Traveling Salesman Problem[J].Computer Engineering,2011,37(10):284-286. |
| |
| Authors: | QIU Wei-xing WANG Shu-rong CHENG Dong-cai XING Xiao-wei CHEN Chun-ling JIANG Dong jian |
| |
| Affiliation: | (School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210003,China) |
| |
| Abstract: | This paper proposes the thought of getting the edges of exact solution to access the approximate solution of the whole Traveling Salesman Problem（TSP）.On the basic of the thought,a new algorithm called collision algorithm is designed.Experiments with the test data from internationally accepted TSPLIB in different cities and size show that the results got through the algorithm is the same or similar with current optimal solution.The algorithm can apply the TSP on a large scale as well as small scale ones. |
| |
| Keywords: | Traveling Salesman Problem（TSP） triangulation combinatorial optimization collision algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
|
