An analogue approach to the travelling salesman problem using an elastic net method.
The travelling salesman problem is a classical problem in the field of combinatorial optimization, concerned with efficient methods for maximizing or minimizing a function of many independent variables. Given the positions of N cities, which in the simplest case lie in the plane, what is the shortest closed tour in which each city can be visited once? We describe how a parallel analogue algorithm, derived from a formal model for the establishment of topographically ordered projections in the brain, can be applied to the travelling salesman problem. Using an iterative procedure, a circular closed path is gradually elongated non-uniformly until it eventually passes sufficiently near to all the cities to define a tour. This produces shorter tour lengths than another recent parallel analogue algorithm, scales well with the size of the problem, and is naturally extendable to a large class of optimization problems involving topographic mappings between geometrical structures.
D000465:Algorithms; D000818:Animals; D006801:Humans; D008433:Mathematics; D008959:Models, Neurological; D009474:Neurons / Q000502:physiology*; D011340:Problem Solving