Format

Send to

Choose Destination
Nature. 1987 Apr 16-22;326(6114):689-91.

An analogue approach to the travelling salesman problem using an elastic net method.

Abstract

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.

PMID:
3561510
DOI:
10.1038/326689a0
[Indexed for MEDLINE]

Supplemental Content

Full text links

Icon for Nature Publishing Group
Loading ...
Support Center