Travelling salesman variation in python

[Erlend Andreas Garberg]

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