Concurrent Neural Network Algorithm for the Traveling Salesman Problem

摘要

A binary neuromorphic data structure is used to encode the N-city Traveling Salesman Problem (TSP). In this representation, the computational complexity, in terms of number of neurons, is reduced from Hopfield and Tank's 0(N sup 2 ) to 0(N log sN). A continuous synchronous neural network algorithm in conjunction with the Lagrange multiplier, is used to solve the problem. The algorithm has been implemented on the NCUBE hypercube multiprocessor. This algorithm converges faster and has a higher probability to reach a valid tour than previously available results. 22 refs., 3 figs., 2 tabs. (ERA citation 13:029811)