求解TSP问题的多级归约算法.PDF
文本预览下载声明
1000-9825/2003/14(01)0035 ©2003 Journal of Software 软 件 学 报 Vol.14, No.1
∗
求解 TSP 问题的多级归约算法
1,2+ 1,2 1,2 1,2,3
邹 鹏 , 周 智 , 陈国良 , 顾 钧
1( 中国科学技术大学 计算机科学技术系,安徽 合肥 230026)
2( 国家高性能计算中心(合肥),安徽 合肥 230026)
3(香港科技大学 计算机科学与技术系,香港)
A Multilevel Reduction Algorithm to TSP
ZOU Peng1,2+, ZHOU Zhi1,2, CHEN Guo-Liang1,2, GU Jun1,2,3
1(Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China)
2(Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China)
3(Department of Computer Science and Technology, Hong Kong University of Science and Technology, Hong Kong, China)
+ Corresponding author: Phn: 86-551-3603747, Fax: 86-551-3601013, E-mail: zouchar@
/~zouchar
Received 2001-07-17; Accepted 2001-12-27
Zou P, Zhou Z, Chen GL, Gu J. A multilevel reduction algorithm to TSP. Journal of Soft ware, 2003,14(1):
35~42.
Abstract: The TSP (traveling salesman problem) is one of the typical NP-hard problems in combinatorial
optimization problem. The fast and effective approximate algorithms are needed to solve the large-scale problem in
reasonable computing time. The known approximate algorithm can not give a good enough tour for the larger
instance in reasonable time. So an algorithm called multilevel reduction algorithm is proposed, which is based on
the analysis of the relation of local optimal tour and global optimal tour of the TSP. The partial tour of the global
optimal tour is obtained by a very high probability through simply intersecting the local optimal tours. Using these
partial tours it could contract the searching space
显示全部