jbn@SU-GLACIER.ARPA.UUCP (06/15/86)
There is a well-known and fast method for finding near-optimum
solutions to the travelling salesman problem. It was discovered at
Bell Labs in the 1960s, and it is as follows:
1. Connect up all N points in some arbitrary order,
resulting in a path with N-1 edges and two endpoints.
2. Pick two edges at random. Cut the path at these points.
This produces three paths, each with two endpoints.
3. There are six possible ways to connect the paths into
a single path. Try all six, and compute the total
distance for each arrangement. Keep the arrangement
with the shortest total length.
4. Iterate steps 2 and 3 until no improvement is observed
for a reasonable number of iterations, at least N
but less than N*N.
I strongly suspect that the neural nets people have just rediscovered
this classic algorithm, especially since the Business Week article
mentions that the neural net approach produces near-optimal, not
optimal, paths. Comparisons with the brute-force solution are
misleading.
John Nagle
[While the Hopfield-net solution may well be based on similar
mathematics, the flavor is quite different. It is more of a
parallel "relaxation" process or fuzzy linking, with each node
trying to link to neighbors in proportion to their nearness.
Hopfield describes this as an analog process that cuts through
the space of possibilities instead of moving around the outside
as the iterative solutions do. The net quickly approaches a
stable configuration of intersecting cliques (if that's not a
contradiction) separated by longer paths, then the cliques fight
it out to determine the final route. (The establishment of one
clique disrupts others, so a slow gradient search for the optimum
is necessary.) The lack of guaranteed optimality is primarily due
to the initial rapid convergence -- it is possible to construct
problems for which the true optimum is quite far from any broad
"potential well" that would attract the system. Some algorithms
use randomized "stochastic anealing" to get around this, others
start the process many times from very different initial conditions,
others just ignore the problem.
For an interesting study of one such problem, see the Spring 1985 issue
of Abacus. It presents a lengthy analysis of Lee Sallows' custom-built
hardware for solving pangram puzzles by full search, then a short article
by John Letaw showing how the same puzzles can (usually!) be solved by
approximation/optimization on a microcomputer running BASIC. -- KIL]