Subj : Re: Travelling Salesman problem -- Finding shortest path in ship warehouse
To   : comp.programming
From : Mike
Date : Wed Aug 17 2005 01:56 pm

In article <ddts0h$gl7$1$8300dec7@news.demon.co.uk>, rkww@rops.org says...
> "Willem" <willem@stack.nl> wrote in message 
> news:slrndg4ptf.1ug3.willem@toad.stack.nl...
> > Roger wrote:
> > ) Consider a park filled with hills and valleys. How would you find the
> > ) deepest point?
> > )
> > ) One way would be to randomly drop footballs and see where they roll to. 
> > The
> > ) more footballs you drop the more likely it is that you'll find one near 
> > the
> > ) bottom.
> > )
> > ) But the only way you can be sure you've got the deepest point is to 
> > check
> > ) out every point in turn.
> > )
> > ) Simulated annealing is essentially the same mechanism: pick a random 
> > start
> > ) point and see how it can be improved by making small, local changes.
> >
> > AIUI, Simulated annealing isn't as much like dropping footballs into a 
> > park
> > filled with hills and valleys, it's more like sending in a kid with ADHD:
> >
> > At first he's really excited and randomly runs up and down hills, but 
> > after
> > a while he gets tired and tends to go downhill more and more, and uphill
> > less and less.  After a while he's so tired he can only go downhill, and
> > then he'll reach one of the valleys.
> >
> >
> > The rough idea is that in the beginning, he'll tend to ignore smaller 
> > bumps
> > but will tend to end up running around in the deeper large-scale valley.
> > After a while he tends to focus on smaller scale valleys until he gets to
> > the smallest scale.
> >
> > But that's an uneducated opinion (as in: I heard it explained to me once).
> >
> >
> > (For pedants, the boy-with-ADHD is actually molecules that cool down and
> > bounce around less and less, IIRC)
> 
> I like footballs :-) Start off with a very bouncy football, so when you 
> first drop it the chances are it will bounce back out off all but the 
> deepest of valleys. Over time, make it less bouncy. Eventually it will get 
> trapped in a valley that's deeper than its current bounce height. But it 
> will still be able bounce out of smaller sub-valleys.
> 
I prefer pizza.  Start with an unlimited supply of pizza with random flavours and a finite supply of very hungry 
piglets. At first the piglets eat anything, but as they slowly fill up they have less time for the brussel-sprout or 
ear-0wax flavoured pizza and more time for the Hawaiian or Cajun chicken pizza. Simulated annealing predicts that the 
last mouthful eaten by the last piglet will be chosen from one of the most tasty pizzas.

Mike

.