Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!rutgers!njin!princeton!phoenix!bogey!mbkennel
From: mbkennel@bogey.Princeton.EDU (Matthew B. Kennel)
Newsgroups: comp.ai.neural-nets
Subject: Re: implementation of "traveling salesman algorithm" on connection machine
Keywords: TSP, connection machine
Message-ID: <6173@phoenix.Princeton.EDU>
Date: 7 Feb 89 05:29:01 GMT
References: <1637@cps3xx.UUCP> <1233@usfvax2.EDU>
Sender: news@phoenix.Princeton.EDU
Reply-To: mbkennel@bogey.UUCP (Matthew B. Kennel)
Distribution: usa
Organization: Princeton University, Princeton NJ
Lines: 70

In article <1233@usfvax2.EDU> pollock@usfvax2.UUCP (Wayne Pollock) writes:
>Funny you should ask; we spent an entire lecture today discussing this
/very problem in my Parallel Processing and Distributed Computing class.
>The short answer is for M cities, an M X M neural network can find very
>close to optimal solutions in a very short time.  In AT&T Bell Labs, I've
>heard that they have designed hardware, had it manufactured, and used it
>to find the solution for a large problem.  The whole time used (including
>manufaturing the chip) was less than the time it took using traditional
>methods on a Cray-1!  (I am assuming that if the story is true, the
>Cray-1 method found an optimal solution; even so, this is impressive!)
>
>(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.
>
>Wayne Pollock (The MAD Scientist)	pollock@usfvax2.usf.edu
>Usenet:		...!{uflorida, codas}!usfvax2!pollock
>GEnie:		W.POLLOCK


I took professor Eric Baum's seminar in neural computation this past
semsester, and I recall reading a paper in which the authors were unable
to reproduce Hopfield & Tank's results in the TSP case; they even used a
scanner to analyze the published graph of H & T's cities and use their
exact coordinates (up to some limits, of course) but couldn't find as
good a solution as Hopfield and Tank claimed.  In other cases, they
claimed that they could not find as good tours either.  Unfortunately, I
don't remember the authors, but I believe the paper was titled something
like "On the Stability of Hopfield and Tank's Solution to the TSP
Problem".  

My judgement is totally neutral---I know Prof. Hopfield is an excellent
and honest scientist---but I thought I should add that there may be a
second side to the story.

Also, I believe there are some indications that the TSP problem is, for
some reasons or another, "easier" than some other kinds of interesting
problems and perhaps the proposed solutions do not translate as well.
(this is hearsay)


Matt Kennel

(this is line counter fodder)