Travelling salesman variation in python

[Peter Hansen]

Erlend Andreas Garberg wrote:

> In article <c4ho3l$4he$1 at news.service.uci.edu>, Josiah Carlson wrote:
> 
>>Look at current TSP algorithms, and exchange their minimization rutines 
>>for a maximization rutine.  TSP is an NP-hard problem, which means that 
>>there is no currently known algorithm for solving it in polynomial time. 
>>  You can approximate it or do a search on the solution space, but 
>>solving it requires searching basically all of the solution space.
> 
> An approximate solution would be good enough, do you have any 
> suggestions about how do do that?

I haven't tried it for such a case, but have you considered a
genetic algorithm approach?  Since you say an approximate solution
is good enough, I would think a GA could vastly shrink the search
space that has to be covered to get "close", assuming that data is
not such that hidden somewhere in it is a single link which has
an associated number that is vastly higher than the others.  (That
would tend to make the GA search even worse than a brute force
approach.)

-Peter