[1]GAO Shang,FANG Jing.A polynomial approximation algorithm for the traveling salesman problem[J].CAAI Transactions on Intelligent Systems,2010,5(4):342-346.
Copy

A polynomial approximation algorithm for the traveling salesman problem

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 5 Number of periods: 2010 4 Page number: 342-346 Column: 学术论文—人工智能基础 Public date: 2010-08-25
Title:
A polynomial approximation algorithm for the traveling salesman problem
Author(s):
GAO Shang;  FANG Jing
School of Computer and Engineering, Jiangsu University of Science and Technology, Zhenjiang 212003, China
Keywords:
expansion method;  shrink method;  traveling salesman problem
CLC:
TP301.6
DOI:
-
Abstract:
The traveling salesman problem (TSP）is a typical combinational optimization problem which is easy to describe and hard to solve. For largescale TSP problems, an effective solution has yet to be found. To improve the time performance of the elastic net method in solving large scale TSPs, faster algorithms were investigated. Use of the elastic net method, the expansion method and the shrink method were proposed. The time complexities of these algorithms were less than O(N3) . After comparison and analysis it was clear that the results of the expansion method were comparatively ideal. Based on analysis of the expansion method, a stochastic expansion method and a complete expansion method were developed. The time complexity of the complete expansion method was less than O(N4), and it was still a polynomial algorithm. Practical examples showed that the complete expansion method is fast and efficient.
References:
［1］邢文循，谢金星.现代优化计算方法［M］.北京：清华大学出版社，1999：90-129.
［2］高国华，沈林成，常文森. 求解TSP问题的空间锐化模拟退火算法［J］.自动化学报，1999,25(3):425-428.
GAO Guohua, SHEN Lincheng, CHANG Wensen. Using simulated annealing algorithm with search space sharpening to solve traveling salesman problem［J］. Acta Automatica Sinica, 1999， 25(3): 425-428.
［3］KIRKPATRICK S, GELATT J R，VECCHI J R. Optimization by simulated annealing［J］. Science， 1983, 220: 671-680.
［4］康立山，谢云，尤矢勇，等.模拟退火算法［M］.北京：科学出版社，1994：150-151.
［5］谢胜利，唐敏，董金祥.求解TSP问题的一种改进的遗传算法［J］.计算机工程与应用，2002,38（8）：58-60.
XIE Shengli, TANG Min, DONG Jinxiang. An improved genetic algorithm for TSP problem［J］.Computer Engineering and Applications, 2002, 38（8）： 58-60.
［6］喻镝，凌捷，谢晓峰.用遗传算法求解CTSP［J］.广东工业大学学报，2000, 17（5）： 52-55.
?YU Di, LING Jie, XIE Xiaofeng. Solving CTSP with genetic algorithm［J］. Journal of Guangdong University of Technology, 2000， 17(5)： 52-55.
［7］张立明.人工神经网络的模型及其应用［M］.上海:复旦大学出版社，1994：97-98.
［8］吴庆洪，张纪会，徐心和.具有变异特征的蚁群算法［J］.计算机研究与发展，1999,36(10)： 1240-1245.
WU Qinghong, ZHANG Jihui, XU Xinhe. An ant colony algorithm with mutation features［J］. Journal of Computer Research and Development, 1999, 36(10)： 1240-1245.
［9］马良，项培军.蚂蚁算法在组合优化中的应用［J］.管理科学学报，2001, 4(2)： 32-37.
MA Liang, XIANG Peijun. Applications of the ant algorithm to combinatorial optimization［J］.Journal of Management Sciences in China, 2001， 4(2)： 32-37.
［10］DURBIN R, WILLSHAW D. An analogue approach to the traveling salesman problem using an elastic net method［J］. Nature, 1987, 326: 689-691.
［11］白艳萍,胡红萍.一个改进的弹性网络算法求解TSP问题［J］.华北工学院学报,2005, 26(4): 235-238.
BAI Yanping, HU Hongping. A modified elastic net algorithm for traveling salesman problem［J］. Journal of North China Institute of Technology, 2005, 26(4): 235-238.
Similar References:

Memo

-

Last Update: 2010-09-20

Copyright © CAAI Transactions on Intelligent Systems