Auto Waves Approach For Solving Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is a typical optimization problem, which belongs to a large family of problems classified as NP-complete. It has the important project background. This paper deals with TSP by transform TSP to a special Shortest Path Problem. Passing through the construction of a special coupled neural network, which can mimic the autowaves in the Pulse-Coupled Neural Networks (PCNNs), we present a new approach (auto waves approach) for solving TSP. The autowaves spread in the network, and the path which the first arrived at the end point from the start point has passed is the optimal answer to the Shortest Path Problem. And then we find the answer to the TSP. This paper discussed the construction of neural networks, and then involves the coupled character in the neural networks, wave theory, multiple waves, and route marker. Comparison with traditional method, the auto waves method can always find the optimal answer to the TSP. This paper also shows the time and space complexity of the auto waves approach. Finally, experiments on solving TSP are presented.