Travelling salesman variation in python

[David M. Cooke]

At some point, Nick Craig-Wood <ncw at axis.demon.co.uk> wrote:

> Peter Maas <peter.maas at mplusr.de> wrote:
>>  Nick Craig-Wood wrote:
>> > I used Simulated Annealing - have a search for the term and you'll see
>> > plenty of references.  Its good at finding a (local) minimum.
>> 
>>  I used to think that Simulated Annealing avoids local traps and
>>  is good at finding a global minimum, at least with a certain
>>  probability that depends on some temperature function. Am I wrong?
>
> You aren't wrong...  It does avoid local traps - that is what the
> simulated annealing bit is for - but it isn't guaranteed to find the
> global minimum otherwise you'd have solved an NP-complete problem in
> polynomial time...

With the right cooling schedule simulated annealing *is* guaranteed to
find the global minimum.

Mind you, that cooling schedule is very slow: the temperature of the
n'th step is T_n = T0/log(n). To get to 1% of your initial
temperature, you'll need about 1e10 steps... polynomial time it ain't.

Most SA cooling schedules you'll see use a quench (T_n = T0*a**n for
some a) or a Cauchy distribution (T_n = T0/n) which are faster, but
aren't guaranteed to give you a global minimum.

-- 
|>|\/|<
/--------------------------------------------------------------------------\
|David M. Cooke
|cookedm(at)physics(dot)mcmaster(dot)ca