| 一种求解平面旅行商问题的新算法——绕中心周游法 |
| |
| 引用本文： | 宇德明.一种求解平面旅行商问题的新算法——绕中心周游法[J].科技导报(北京),2007,25(15):53-57. |
| |
| 作者姓名： | 宇德明 |
| |
| 作者单位： | 中南大学土木建筑学院,长沙,410075 |
| |
| 摘 要： | 提出了一种求解平面旅行商问题的新算法——绕中心周游法,它是一种确定型算法,时间复杂性与最近邻算法相同,为O(n2),其中n为城市数。利用所编写的绕中心周游法和最近邻算法程序,对不同规模的平面旅行商问题进行了数值试验,对两种算法的求解质量进行了对比分析。结果表明:①绕中心周游法和最近邻算法求解质量的相对优劣取决于具体问题中城市的数量和分布;②对于4城市问题,绕中心周游法总能得到最优解,而最近邻算法经常不能得到最优解;③对于小规模(n<20)问题,绕中心周游法的求解质量一般优于最近邻算法的求解质量;④对于中等规模(20≤n≤30)问题,绕中心周游法的求解质量总体上相当于最近邻算法的求解质量;⑤对于大规模(n>30)问题,绕中心周游法的求解质量一般次于最近邻算法的求解质量。
|
| 关 键 词： | 平面旅行商问题 绕中心周游法 数值试验 最近邻算法 对比分析 |
| 文章编号： | 1000-7857（2007）15-0053-05 |
| 修稿时间： | 2007-06-15 |
A New Algorithm for Solving Plane Travelling Salesman Problem:Travelling-around-the-center Method |
| |
| YU Deming.A New Algorithm for Solving Plane Travelling Salesman Problem:Travelling-around-the-center Method[J].Science & Technology Review,2007,25(15):53-57. |
| |
| Authors: | YU Deming |
| |
| Institution: | College of Civil Engineering and Architecture, Central South University, Changsha 410075, China |
| |
| Abstract: | |
| |
| Keywords: | plane travelling salesman problem travelling-around-the-center method numerical tests nearest neighbor algorithm comparison analysis |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
