Solving the TSP problem with a crystal algorithm
Cai Dong-feng · Caai Transactions on Intelligent Systems · 2008
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(knlogn)complexity.It can also be used in parallel computation,generating real-time solutions for open-looped,dynamic,and large-scale TSP problems.