Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!decwrl!deccrl!bloom-beacon!eru!hagbard!sunic!mcsun!hp4nl!fwi.uva.nl!smagt
From: smagt@fwi.uva.nl (Patrick van der Smagt)
Newsgroups: comp.ai.neural-nets
Subject: Re: Travelling Salesman problem
Message-ID: <1991Apr15.192648.535@fwi.uva.nl>
Date: 15 Apr 91 19:26:48 GMT
References: <1991Apr12.162922.4749@nlm.nih.gov>
Sender: news@fwi.uva.nl
Organization: FWI, University of Amsterdam
Lines: 60
Nntp-Posting-Host: wendy.fwi.uva.nl

chrisk@nlm.nih.gov (Christopher Y. Kim) writes:

>A couple of us medical students in medical informatics heard a lecture
>on neural nets where Dr. Nicholas DeCleris from Maryland mentioned something
>about using a neural network to solve the travelling salesman problem,

The first person to SOLVE tsp earns the Nobel prize for maths, I'm sure.
The rumour you've caught concerns a `novel' approximation of tsp.  The
primary reference is the Hopfield and Tank article,

%A J. J. Hopfield
%A D. W. Tank
%D 1985
%J Biological Cybernetics
%V 52
%P 141--152
%T `Neural' computation of decisions in optimization problems

And from then on articles spring up like mushrooms.  Theoretically,
it is very nice, but practically it doesn't come near the Lin
& Kernighan (1973) algorithm.  A comparison which I found I don't
know where (to be fed through LaTeX):

\begin{tabular}{l||r|r|c}
Algorithm & \# cities & good & runtime (400 cities) \\\hline\hline
L--K	  & 50,000    & 2\%  & 20s                  \\\hline
Hopfield  & 30        & 17\% & $6\cdot60\cdot60s$     \\\hline
\end{tabular}


There are quite a few improvements on H&T, such as

%A A. Joppe
%A H. R. A. Cardon
%A J. C. Bioch
%T A neural network for solving the travelling salesman problem on
the basis of city adjacency in the tour
%D 1990
%B ICANN
%C Paris

but still, a long way far from L&K.

						Patrick van der Smagt 
								    /\/\
                                                                    \  /
Organisation: Faculty of Mathematics & Computer Science             /  \
              University of Amsterdam, Kruislaan 403,            _  \/\/  _
              NL-1098 SJ  Amsterdam, The Netherlands            | |      | |
Phone:        +31 20  525 7524                                  | | /\/\ | |
Fax:          +31 20  525 7490                                  | | \  / | |
                                                                | | /  \ | |
email:        smagt@fwi.uva.nl                                  | | \/\/ | |
                                                                | \______/ |
                                                                 \________/

								    /\/\
``The opinions expressed herein are the author's only and do        \  /
not necessarily reflect those of the University of Amsterdam.''     /  \
                                                                    \/\/