This applet attempts to solve the traveling salesman problem by
simulated annealing. In the black window
one can select a set of cities in the following manner. Click in it
with the mouse. A small dot depicting a city will appear. Repeat until
you think you have enough cities. Note that the city counter has
increased while doing so. Another method is to set the city counter
with a number and then press the button `zap' or `grid'. If desired
one can add a few more cities with the mouse. The number of cities
should be below 100, otherwise the program becomes very slooooow...
When you are happy with
the arrangement push `start'. A path will appear which is usually far
from shortest. However, it will gradually improve. If so
desired one can stop the process to change the temperature. Unfortunately the program's reaction to the stop
button is often slow, especially with more than 50
cities. So be patient. A good
starting temperature is T about 10 or 20. The value T=0 forces a greedy
behaviour of the system, in which it is easy to get stuck in local minima.
When T>50 you really cook the system to get only randomish paths.
To leave the process altogether push `stop' and then `reset'. The
city counter is then set to zero and you can start all over again.
This applet is only an attempt to learn a little about simulated
annealing. Anyone interested in REAL SOFTWARE for solving TSP
and some history around the problem should definitely look
at William Cook's
TSP-site,/a>.
Back to my Homepage.