-
题名一种求解平面旅行商问题的新算法——绕中心周游法
- 1
-
-
作者
宇德明
-
机构
中南大学土木建筑学院
-
出处
《科技导报》
CAS
CSCD
2007年第15期53-57,共5页
-
文摘
提出了一种求解平面旅行商问题的新算法——绕中心周游法,它是一种确定型算法,时间复杂性与最近邻算法相同,为O(n2),其中n为城市数。利用所编写的绕中心周游法和最近邻算法程序,对不同规模的平面旅行商问题进行了数值试验,对两种算法的求解质量进行了对比分析。结果表明:①绕中心周游法和最近邻算法求解质量的相对优劣取决于具体问题中城市的数量和分布;②对于4城市问题,绕中心周游法总能得到最优解,而最近邻算法经常不能得到最优解;③对于小规模(n<20)问题,绕中心周游法的求解质量一般优于最近邻算法的求解质量;④对于中等规模(20≤n≤30)问题,绕中心周游法的求解质量总体上相当于最近邻算法的求解质量;⑤对于大规模(n>30)问题,绕中心周游法的求解质量一般次于最近邻算法的求解质量。
-
关键词
平面旅行商问题
绕中心周游法
数值试验
最近邻算法
对比分析
-
Keywords
plane travelling salesman problem
travelling-around-the-center method
numerical tests
nearest neighbor algorithm
comparison analysis
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-