for the Travelling Salesman Problem

The elastic net is a kind of artificial neural networks which is used for optimization problems. |

Let us demonstrate the elastic net method on a simple example
of solving *a travelling salesman problem.* *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, what is the
shortest
closed tour in which each city can be visited once? **

All exact methods known for determining an optimal route
require a computing effort that increases exponentially with
number of cities, so in practice exact solutions can be attempted
only on problems involving a few hundred cities or less. *The
travelling salesman problem *belongs to the large class of
nondeterministic polynomial time complete problems.

The elastic net method has been applied to *the travelling
salesman problem*. The essence of the method is:

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.

A tour can be viewed as a mapping from a circle to the plane so that each city in the plane is mapped to by some point on the circle. We consider mappings from a circular path of points to the plane in which neighboring points on the circle are mapped as close as possible on the plane. This is a special case of the general problem of best preserving neighborhood relations when mapping between different geometrical spaces.

The algorithm is a procedure for the successive recalculation of the positions of a number of points in the plane in which the cities lie. The points describe a closed path which is initially a small circle centered on the center of the distribution of cities and is gradually elongated non-uniformly to pass eventually near all the cities and thus define a tour around them. Each point on the pass moves under the influence of two types of force:

**1.** the first moves it
towards those cities to which it is nearest;

**2.** the second pulls it
towards its neighbors on the path, acting to minimize the total
path length.

By this means, each city becomes associated with a particular
section on the path. The tightness of the association is
determined by how the force contributed from a city depends on a
distance, and the nature of this dependence changes as the
algorithm progresses. Initially all cities have roughly equal
influence on each point on the path. Subsequently, longer
distance become less favored, and each city gradually becomes
more specific for the points on the path closest to it.

**THE TRAVELING SALESMAN
PROBLEM**

If you were using a
Java-enabled browser, you would see Travelling Salesman Problem
demonstration instead of this paragraph.