Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!decwrl!labrea!glacier!jbn
From: jbn@glacier.STANFORD.EDU (John B. Nagle)
Newsgroups: comp.ai.neural-nets
Subject: Re: implementation of "traveling salesman algorithm" on connection machine
Summary: Neural net proponents attack straw man
Keywords: TSP, connection machine
Message-ID: <18090@glacier.STANFORD.EDU>
Date: 7 Feb 89 17:56:42 GMT
References: <1637@cps3xx.UUCP> <1233@usfvax2.EDU> <6173@phoenix.Princeton.EDU>
Distribution: usa
Organization: Stanford University
Lines: 28

In article <1233@usfvax2.EDU> pollock@usfvax2.UUCP (Wayne Pollock) writes:
>(Quoted without permission from my class notes (by Dr. Stark:)
>Hopfield and Tank[1985] describe a case involving over 100 cities in which
>a neural network computes a solution which is only a fraction of 1% longer
>than the optimal solution, in only a few milliseconds of computation.  They
>remark that it would have taken weeks to have found an optimal solution
>even using a Cray.

       The same hype appeared in an article in Business Week.  Comparing
the time required to find a near-optimum solution with a hardware neural
net to that required to find an optimal solution on a Cray is misleading,
if not fraudulent.  While finding an optimal solution is expensive,
finding a near-optimal solution on a digital computer is quite efficient.  
I can get solutions for a 100-node network on an IBM PC/AT (6MhZ!) in well 
under two minutes, using the Bell Labs algorithm.  This is the right result 
to compare with the neural net, not the brute-force optimal solution.

       The algorithm is quite simple.  Construct an arbitrary path connecting
all the nodes.  Compute its length.  Attempt to shorten the path by picking
two random edges on the path, and cut the path into three sections 
by removing those edges.  Try the paths that can be constructed from the 
three sections and pick the one with the shortest length.  That path 
becomes the current working path.  Iterate the shortening process until
no improvement is observed for some length of time.  Output the working path.

       You don't need a Connection Machine for this.

					John Nagle