Travelling salesman variation in python

[Mitja]

"Diez B. Roggisch" <deetsNOSPAM at web.de> wrote in message
news:c4jk1t$2k9keu$1 at ID-111250.news.uni-berlin.de...
> You could go for local search. First, create a randow tour. Then select a
> neighborhood. Find the local minimum for that neighborhood. Do this as
> often as you like.
>
> A typical neighborhood for tsps are four nodes where two of them are
> adjacent in your tour. Then  exchange the nodes so that they still form a
> tours. If that has less costs, keep it that way.
>
> --n1--n2--
> --n3--n4--
>
> becomes
>
> --n1\/n2--
> --n3/\n4--
>


This is more or less just one of the things you'd do with simulated
annealing. And with such a "randomized" problem, this is certainly the one
and only way to go. If there are no rules defining the structure of the
graph, you can't write an optimized code which takes these rules into
account. Anyway, SA is what you want. Google for it, use it.

Mitja