- **Python**
(*http://www.velocityreviews.com/forums/f43-python.html*)

- - **Travelling salesman variation in python**
(*http://www.velocityreviews.com/forums/t329418-travelling-salesman-variation-in-python.html*)

Travelling salesman variation in pythonHi!
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 |

Re: Travelling salesman variation in python> I would appreciate some comments on this :)
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. - Josiah |

Re: Travelling salesman variation in pythonIn article <c4ho3l$4he$1@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. > > - Josiah An approximate solution would be good enough, do you have any suggestions about how do do that? -- mvh Erlend Garberg erlendga@ifi.uio.no |

Re: Travelling salesman variation in pythonErlend Andreas Garberg <erlendga@tva.ifi.uio.no> writes:
> An approximate solution would be good enough, do you have any > suggestions about how do do that? Is it just an arbitrary graph? Most TSP approximation algorithms depend e.g. on the triangle inequality, i.e. d(A,C) <= d(A,B) + d(B,C). Papadimitriou and Stieglitz, "Combinatorial Optimization" was a standard textbook on this stuff, though is pretty old by now. |

Re: Travelling salesman variation in pythonIn article <7xhdw3zfb2.fsf@ruckus.brouhaha.com>, Paul Rubin wrote:
> Erlend Andreas Garberg <erlendga@tva.ifi.uio.no> writes: >> An approximate solution would be good enough, do you have any >> suggestions about how do do that? > > Is it just an arbitrary graph? Most TSP approximation algorithms > depend e.g. on the triangle inequality, i.e. d(A,C) <= d(A,B) + d(B,C). > > Papadimitriou and Stieglitz, "Combinatorial Optimization" was a > standard textbook on this stuff, though is pretty old by now. The graph is arbitrary, yes.. -- mvh Erlend Garberg erlendga@ifi.uio.no |

Re: Travelling salesman variation in pythonHello 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@tva.ifi.uio.no> schrieb im Newsbeitrag news:slrnc6on9h.spl.erlendga@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 > |

Re: Travelling salesman variation in pythonCan't TSP be converted to your problem?
If you have TSP with distance(Xi, Xj)=Dij, then convert it to your problem by letting distance(X'i, X'j)=distance(X'j, X'i)=-Dij. or if only positive weights are allowed then use max(D)-Dij. Jeff |

Re: Travelling salesman variation in python> An approximate solution would be good enough, do you have any
> suggestions about how do do that? One approximate solution to the TSP is the bitonic TSP. That is, start at the leftmost point, find a path to the rightmost point, then find a return path to the leftmost point. Search for 'optimal bitonic tsp' in google, the second entry will have pseudocode for the algorithm. I've personally converted it to Python for other uses, but I'll leave it as an exercise for you. You can convert it into your 'maximum' by changing the line: if q < b[j - 1, j] then to: if q > b[j - 1, j] then - Josiah |

Re: Travelling salesman variation in pythonErlend Andreas Garberg <erlendga@tva.ifi.uio.no> wrote:
> 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 had to solve exactly this problem when I was at University (many moons ago now ;-) I used Simulated Annealing - have a search for the term and you'll see plenty of references. Its good at finding a (local) minimum. Just be glad you don't have to write it in Fortran like I did! -- Nick Craig-Wood ncw@axis.demon.co.uk |

Re: Travelling salesman variation in pythonIn article <c4ialj$mcq$1@news.service.uci.edu>, Josiah Carlson wrote:
> One approximate solution to the TSP is the bitonic TSP. That is, start > at the leftmost point, find a path to the rightmost point, then find a > return path to the leftmost point. The problem is that all nodes are connected to all the other nodes, and the weights are in essence random.. So it won't be possible to find leftmost/rightmost point. -- mvh Erlend Garberg erlendga@ifi.uio.no |

All times are GMT. The time now is 05:56 PM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.