Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   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)

Erlend Andreas Garberg 04-01-2004 06:19 PM

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


Josiah Carlson 04-01-2004 06:44 PM

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

Erlend Andreas Garberg 04-01-2004 06:53 PM

Re: Travelling salesman variation in python
 
In 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


Paul Rubin 04-01-2004 07:08 PM

Re: Travelling salesman variation in python
 
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.

Erlend Andreas Garberg 04-01-2004 07:12 PM

Re: Travelling salesman variation in python
 
In 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


GŁnter Jantzen 04-01-2004 08:20 PM

Re: Travelling salesman variation in python
 
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@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
>




Jeff Epler 04-01-2004 08:55 PM

Re: Travelling salesman variation in python
 
Can'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


Josiah Carlson 04-02-2004 12:00 AM

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

Nick Craig-Wood 04-02-2004 10:30 AM

Re: Travelling salesman variation in python
 
Erlend 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

Erlend Andreas Garberg 04-02-2004 10:55 AM

Re: Travelling salesman variation in python
 
In 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.