Another innovation made by Hopfield was to show how to solve
large combinatorial optimisation problems on neural nets
[Hopfield and Tank, 1985]. The classical example of this is the so-
called Travelling salesman Problem (TSP). Here, a travelling salesman
has to visit each of a set of cities in turn in such a way as to
minimise the total distance travelled. Each city must be visited once
and only once. This kind of problem is computationally difficult in a
technical sense (NP-complete) in that the time to solution scales with
the number cities faster than the time raised to any fixed power
and therefore might scale like
.
The solution of the TSP consists of a sequence of cities. The problem for N cities may be coded into an N by N network as follows. Each row of the net corresponds to a city. The position of the city in the solution sequence is given by putting a `1' at the corresponding place in the row and 0's everywhere else in that row. Thus, if the city corresponding to row 5 was 7th in the sequence there would be a 1 in the 7th place of the 5th row and zeros everywhere else. Note that most states of the net do not correspond to valid tours - there must be only one `1' per row. The problem then, is to construct an energy function (and hence a set of weights) which lead to stable states (states of lowest energy) of the network that, not only express valid city tours, but which also are tours of short length. The validity criterian results in negative weights (inhibition) between nodes in the same row, and between nodes in the same column. The path-length criterion leads to inhibition between adjacent columns (cities in a path) proportional to the path length between the cities (row positions). The net is now allowed to run until an energy minimum is reached which should now correspond to a solution of the problem.