[1]ZHOU Lan-hai,CAI Dong-feng.Solving the TSP problem with a crystal algorithm[J].CAAI Transactions on Intelligent Systems,2008,3(2):167-172.
Copy

Solving the TSP problem with a crystal algorithm

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 3 Number of periods: 2008 2 Page number: 167-172 Column: 学术论文—人工智能基础 Public date: 2008-04-25
Title:
Solving the TSP problem with a crystal algorithm
Author(s):
ZHOU Lan-hai;  CAI Dong-feng
Knowledge Engineering Research Center, Shenyang Institute of A eronautical Engineering，Shenyang 110034,China
Keywords:
traveling salesman problem; ice crystal; dendrite; convex hull; nondeterministic polynomialm
CLC:
TP301.5
DOI:
-
Abstract:
The traveling salesman problem (TSP) is a typical NP problem. The optimal solution can be costly to obtain as computational requirements of the problem increase exponentially with complexity. This paper proposes a new method for solving TSP problems. With this method, we simulated the growth process of crystals on the surface of a lake as the temperature of the water decreased. In the metastable region we maintained an appropriate degree of saturation and found the growth process of the crystals was the same as the process of forming a TSP path. The proposed method is an appropriate algorithm for solving TSP problems quickly and effectively, obtaining feasible solutions under O(knlogn) complexity. It can also be used in parallel computation, generating realtime solutions for openlooped, dynamic, and largescale TSP problems.
References:
［1］GAREY M R, JOHNSON D S. Computers and intractability :a guide to th e theor y of NPcompleteness ［M］. San Francisco: Freeman W H, 1979.
［2］ DORIGO M, MANIEZZO V, COLORNI A. The ant system: optimization by a colony of cooperating agents［J］. IEEE Transactions on Systems , Man and Cybernetics, 1996(1):2941.
［3］ KENNEDY J, EBERHART R C. Particle swarm optimization ［C］// Proceedings of IE EE International Conference on Neutral Net works,Perth,Australia , 1995: 1942 1948.
［4］ KIRKPATRICK D G, SEIDEL R. The ultimate planar convex hull algorithm［J］. SIAMJ Comput,1986,15:287299.
［5］ 周培德.计算几何：算法分析与设计［M］.北京:清华大学出版社, 2000. ［6］ 徐庭栋.非平衡晶界偏聚动力学和晶间脆性断裂［M］.北京:科学出版社, 2006.
［7］ GERHARD R.TSPLIB ［EB/OL］.［19970219］.http://elib.zib.de/pub/mptestdata/tsp/tsplib/tsplib.html.
［8］ WU Ruiqian, LIN Huijuan,JIANG Fengyi.Final project for neural Network［EB/OL］.［19971228］. http://wayne.cs.nthu.edu.tw/~roland/nn/report_fc.html.
［9］ PEITGEN H O, RICHLET P H. The beauty of fractals: images of complex dyn amical systems［M］. New York:SpringerVerlag,1986.［10］ KENNETH J.分形几何——数学基础及其应用［M］.曾文曲,译.沈阳:东北大学出版社,1991.
［11］陈志平，徐宗本.计算机数学——计算复杂性理论与NP、CNP难问题的求解［M］.北京 :科学出版社, 2001.
Similar References:

Memo

-

Last Update: 2009-05-11

Copyright © CAAI Transactions on Intelligent Systems