Travelling salesman variation in python

[Günter Jantzen]

Hello Erlend,

in my opinion its not a TSP. In TSP problems a minimum is searched, you
search the maximum
And TSP is usually formulated for undirected graphs. So (for me) its not so
clear if the problem is NP

Did you think about trying a greedy algorithm. Start at some point and go
always the way with the highest value and eliminate the previous note

If you want better results, try it with more combinations. For example
choose the three highest values from  every  node and follow this ways if
possible

Use backtracking with recursive calls
(explained in many textbooks about discrete mathematics. Typical example -
the 8 queens problem)

Of course I have no idea if this approch will be helpful

Günter

"Erlend Andreas Garberg" <erlendga at tva.ifi.uio.no> schrieb im Newsbeitrag
news:slrnc6on9h.spl.erlendga at tva.ifi.uio.no...
> Hi!
>
> I'm trying to code a implementation of a variation of the travelling
> salesman problem.
>
> The problem is the following.
>
> I have X nodes.
> Each node has a number assosiated with each of the other nodes.
>
> The problem is then:
> Construct a ring of the nodes so that the sum of the numbers is the
> highest possible.
>
> Example:
> Nodes:
> A with numbers B->1200, C->2000
> B with numbers A->3000, C->4000
> C with numbers A->9000, B->5000
>
> The optimal ring is in this case can f.ex. be:
> A->1200->B->4000->C->9000->A with sum 14200.
>
> I have implemented this in python in the following way:
>
> hash is a dictionary with node-name as key and node-object as value.
> Each node-object has a dictionary speeds with node-name as key and a
> number as value. this dict stores the numbers associated with the other
> nodes.
>
> -------------------------------------------------------------------
> # method xcombinations
> def xcombinations(items, n):
>     if n==0: yield []
>     else:
>         for i in xrange(len(items)):
>             for cc in xcombinations(items[:i]+items[i+1:],n-1):
>                 yield [items[i]]+cc
>
> # help function
> func = lambda x,y: int(hash[x].speeds[y])
>
>
> # code starts here:
> bestcomb = []
> bestspeed = 0
>
>         for comb in xcombinations(hash.keys(),len(hash)):
>             speed = sum(map(func,comb,comb[1:] + comb[:1]))
>             if speed > bestspeed:
>                 bestcomb = comb
>                 bestspeed = speed
>
> -----------------------------------------------------------------
>
> My implementation generate all combinations, and check which gives the
> highest result.
>
> My problem is that when the number of nodes is higher than 8, the
> algorithm slows to a crawl (because of O(n!) complexity). I wonder if
> there is some way I can optimize my algorithm to make it run faster?
> Currently it takes 20 seconds to compute the best combination with 9
> nodes on my hardware.
>
>
> I would appreciate some comments on this :)
>
> --
> Regards
> Erlend Garberg
>