Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uflorida!usfvax2!pollock
From: pollock@usfvax2.EDU (Wayne Pollock)
Newsgroups: comp.ai.neural-nets
Subject: Re: implementation of "traveling salesman algorithm" on connection machine
Keywords: TSP, connection machine
Message-ID: <1233@usfvax2.EDU>
Date: 6 Feb 89 21:55:28 GMT
References: <1637@cps3xx.UUCP>
Reply-To: pollock@usfvax2.UUCP (Wayne Pollock)
Distribution: usa
Organization: University of South Florida at Tampa
Lines: 29

In article <1637@cps3xx.UUCP> artzi@cpsvax.cps.msu.edu (Ytshak Artzi) writes:
>   Does anyone know about any implementation of efficient
>algorithms for the Traveling salesman Problem (TSP) on the
>Connection Machine ?
>  I will appreciate any reference to literature, papers, ideas, etc.
>    Thanks,
>            Izik Artzi
>            CPS, Michigan State U.

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