Subj : Re: Travelling Salesman problem -- Finding shortest path in ship warehouse
To   : comp.programming
From : Willem
Date : Tue Aug 16 2005 11:24 pm

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)



SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

.