Hello, I've been searching for Lisp code to the Traveling Salesman
Problem, but it looks like this problem might be a favorite classroom
assignment -- so no luck.
I'm more interested in using the algorithm than the (undoubtedly worthy)
exercise of developing it. In particular, I'd like to add a constraint
that allows me to choose the starting and ending 'cities'.
Any help appreciated. Thanks!
>Hello, I've been searching for Lisp code to the Traveling Salesman
>Problem, but it looks like this problem might be a favorite classroom
>assignment -- so no luck.
Do you care about speed? This seems like a fairly easy problem if it is
acceptable to generate a list of all permutations of the set of cities
and sort the set of permutations according to total walking distance
(use extremum instead of sort for an efficiency boost). If you are
dealing with a large set of cities, though, that set may be too large.
Coming up with a good heuristic solution (that actually gets the right
answer) would be much harder than brute force. In either case, adding
your constraint about starting and ending cities is trivially easy.
Right -- I've written a brute force solution, but it's incredibly slow.
I just had a hunch that someone out there had might have done it a
little more elegantly.
Eric Lavigne wrote:
>>Hello, I've been searching for Lisp code to the Traveling Salesman
>>Problem, but it looks like this problem might be a favorite classroom
>>assignment -- so no luck.
>
>
> Do you care about speed? This seems like a fairly easy problem if it is
> acceptable to generate a list of all permutations of the set of cities
> and sort the set of permutations according to total walking distance
> (use extremum instead of sort for an efficiency boost). If you are
> dealing with a large set of cities, though, that set may be too large.
> Coming up with a good heuristic solution (that actually gets the right
> answer) would be much harder than brute force. In either case, adding
> your constraint about starting and ending cities is trivially easy.
>
Drew Krause <········@mindspring.com> writes:
> Right -- I've written a brute force solution, but it's incredibly
> slow.
Yep.
> I just had a hunch that someone out there had might have done it
> a little more elegantly.
Nope.
It's an NP-Complete problem. All algorithms to solve the problem take
more than polynomial time, so you are basically out of luck.
--
~jrm
>>>Hello, I've been searching for Lisp code to the Traveling Salesman
>>>Problem
>> I just had a hunch that someone out there had might have done it
>> a little more elegantly.
>Nope.
>It's an NP-Complete problem. All algorithms to solve the problem take
>more than polynomial time, so you are basically out of luck.
So it's impossible, eh? That only makes it more fun to try ^^
Here's my stab at an algorithm. Any guesses for how it scales?
1) Get a good initial guess using heuristic algorithm. This should be a
relatively short distance compared to most guesses, but not necessarily
the shortest. As a crude example, I might have the salesman always go
to the closest node that he hasn't been to yet. Create variables
shortest-path and shortest-distance to store this guess.
2) Start generating the first permutation. With each location added to
the permutation, check whether this might be the shortest path. (I'll
discuss how to eliminate based on a partial permutation later). If an
elimination can be performed on an incomplete permutation, a large
number of matching permutations can be eliminated simultaneously. If
you get to the point of generating a complete permutation, and it is
the fastest solution so far, update shortest-path and
shortest-distance.
3) Repeat until everything eliminated.
Although I can't get an exact value for distance without a complete
permutation, I can put a lower bound on it. For each of the nodes not
yet reached, assume it will take at least the distance to the nearest
untouched node. This should be fairly close to the real answer, since a
shortest path will usually involve only trips between closely
neighboring nodes. Sum these up, combine with the exact distance for
the part of the path that is already known, and you have a fairly high
lower-bound to work with. Most paths will be an order of magnitude
greater than the shortest (imagine bouncing between opposite edges of
the graph), so the vast majority can be culled quickly.
>>>but it looks like this problem might be a favorite classroom
>>>assignment -- so no luck.
>>>I'm more interested in using the algorithm than the (undoubtedly worthy)
>>>exercise of developing it
Competing with my classmates to get the best algorithm on this sounds
like fun. Maybe I should have been a CS major ^^ I'm a bit overloaded
now, though, so I'll pass on this one.
"Eric Lavigne" <············@gmail.com> writes:
>>>>Hello, I've been searching for Lisp code to the Traveling Salesman
>>>>Problem
>
>>> I just had a hunch that someone out there had might have done it
>>> a little more elegantly.
>
>>Nope.
>>It's an NP-Complete problem. All algorithms to solve the problem take
>>more than polynomial time, so you are basically out of luck.
>
> So it's impossible, eh?
Not impossible, just really hard. If you google around you'll find a
lot of info on it. The world record seems to be a solution for 24,978
cities in Sweden. But before you decide to try to beat it, you should
know that it took the equivalent of 91.9 CPU years on an Intel Xeon
running at 2.8 GHz. They used a cluster of 96 dual processor machines
running this as a background task from March 2003 through May 2004.
(Research Team
David Applegate, AT&T Labs - Research
Robert Bixby, ILOG and Rice University
Vasek Chv�tal, Rutgers University
William Cook, Georgia Tech
Keld Helsgaun, Roskilde University )
See http://www.tsp.gatech.edu/index.html
Cook has a program called `Concorde' that solves various TSP
problems. It seems to be able to handle up to around 1000 nodes in a
reasonable amount of time (< 2 minutes or so).
~jrm
"Eric Lavigne" <············@gmail.com> writes:
> So it's impossible, eh? That only makes it more fun to try ^^
> Here's my stab at an algorithm. Any guesses for how it scales?
Hmmm... i didn't analyse your algorithm but it looks like a good
direction. There are branch-and-bound algorithms for TSP that work
OK (at least you can break the loop at any iteration and you
always know how good or bad your current solution is).
But TSP is really hard: There's even no useable approximation
algorithm (polynomial runtime with polynomial bounded
quality). If metric TSP is OK (costs for routes are symetric and
the triangle inequality holds) there are fast (O(n^3)) and good
(quality 3/2 [quality 1 means perfect solution]) approximation
algorithms (for example the algorithom of Christofides).
--
Stefan.
Stefan Nobis wrote:
> "Eric Lavigne" <············@gmail.com> writes:
>
> But TSP is really hard: There's even no useable approximation
> algorithm (polynomial runtime with polynomial bounded
> quality). If metric TSP is OK (costs for routes are symetric and
> the triangle inequality holds) there are fast (O(n^3)) and good
> (quality 3/2 [quality 1 means perfect solution]) approximation
> algorithms (for example the algorithom of Christofides).
>
Which means I'm doubly stuck: I'm using a "city-block" metric, where the
triangle inequality does not hold.*sigh*
My brute force algorithm is do-able to about 10 cities (ca. 30 minutes
on my little laptop). I might try developing an interface with Concorde,
which is really fast.
But thanks to everyone for posting -- I'm learning a lot about this
problem. I had no idea what's involved here!
>Which means I'm doubly stuck: I'm using a "city-block" metric, where the
>triangle inequality does not hold.*sigh*
If by city-block you mean traveling only north, south, east, and west,
and with travel not allowed over some regions, then the triangle
inequality still holds. On the other hand, one-way streets would break
the symmetry requirement for metric TSP.
Drew Krause schrieb:
> My brute force algorithm is do-able to about 10 cities (ca. 30 minutes
> on my little laptop). I might try developing an interface with Concorde,
> which is really fast.
>
> But thanks to everyone for posting -- I'm learning a lot about this
> problem. I had no idea what's involved here!
With TA you should be able to raise your maps up to several hundreds of
cities or even
thousands of cities in less than 30 minutes.
I tried my TA implementation on a randomly generated map of 100 cities
and it found a good
solution in less than 1 minute. This was tested using Lispworks
Personal on my iBook G4 1,2 GHz.
ciao,
Jochen
Drew Krause <········@mindspring.com> writes:
> Eric Lavigne wrote:
>>>Hello, I've been searching for Lisp code to the Traveling Salesman
>>>Problem, but it looks like this problem might be a favorite classroom
>>>assignment -- so no luck.
> Right -- I've written a brute force solution, but it's incredibly
> slow. I just had a hunch that someone out there had might have done it
> a little more elegantly.
Probably. But they keep the sources for themselves.
http://www.itasoftware.com/
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
Drew Krause a �crit :
> Right -- I've written a brute force solution, but it's incredibly slow.
> I just had a hunch that someone out there had might have done it a
> little more elegantly.
Brute force, like enumerate and tests all the candidate solutions ? Must
be very slow indeed ...
There are ways to attack a problem like this with a combination of
forward-checking plus maintenance of arc consistency (see AC family of
algorithms), which helps prune a lot of the dead-ends.
(have a look at http://www.lirmm.fr/~bessiere/stock/ijcai97-gac.ps and
stuff like that)
>
> Eric Lavigne wrote:
>
>>> Hello, I've been searching for Lisp code to the Traveling Salesman
>>> Problem, but it looks like this problem might be a favorite classroom
>>> assignment -- so no luck.
>>
>>
>>
>> Do you care about speed? This seems like a fairly easy problem if it is
>> acceptable to generate a list of all permutations of the set of cities
>> and sort the set of permutations according to total walking distance
>> (use extremum instead of sort for an efficiency boost). If you are
>> dealing with a large set of cities, though, that set may be too large.
>> Coming up with a good heuristic solution (that actually gets the right
>> answer) would be much harder than brute force. In either case, adding
>> your constraint about starting and ending cities is trivially easy.
>>
Drew Krause <········@mindspring.com> writes:
> Hello, I've been searching for Lisp code to the Traveling Salesman
> Problem, but it looks like this problem might be a favorite classroom
> assignment -- so no luck.
>
> I'm more interested in using the algorithm than the (undoubtedly
> worthy) exercise of developing it. In particular, I'd like to add a
> constraint that allows me to choose the starting and ending 'cities'.
>
> Any help appreciated. Thanks!
Out of curiosity, how many cities are we talking about?
--
~jrm
Well, at 12 cities my brute-force algorithm takes hours. At 6 cities it
takes half a second.
Thanks to all who responded -- even if the news was bad. I had to give
it a try!
Joe Marshall wrote:
>
> Out of curiosity, how many cities are we talking about?
>
Drew Krause wrote:
> Hello, I've been searching for Lisp code to the Traveling Salesman
> Problem, but it looks like this problem might be a favorite classroom
> assignment -- so no luck.
>
> I'm more interested in using the algorithm than the (undoubtedly worthy)
> exercise of developing it. In particular, I'd like to add a constraint
> that allows me to choose the starting and ending 'cities'.
>
> Any help appreciated. Thanks!
It's a NP Complete problem isn't it? Meaning it can't be done
efficiently :) If you can do it efficiently you'd be able to break all
internet encryption (just as a starting point)
Someone please correct me on this if I'm wrong?
Kelsin
>It's a NP Complete problem isn't it? Meaning it can't be done
>efficiently :) If you can do it efficiently you'd be able to break all
>internet encryption (just as a starting point)
Internet encryption is analogous to the traveling salesman problem? Or
breaking all internet encryption is just a problem of similar
difficulty? If the former I'd love to hear about it.
Eric Lavigne wrote:
>>It's a NP Complete problem isn't it? Meaning it can't be done
>>efficiently :) If you can do it efficiently you'd be able to break all
>>internet encryption (just as a starting point)
>
>
> Internet encryption is analogous to the traveling salesman problem? Or
> breaking all internet encryption is just a problem of similar
> difficulty? If the former I'd love to hear about it.
>
Well (again people correct me if I'm wrong) but Traveling Salesmen being
an NP Complete problem means that if we could solve it at good speed we
could solve all other NP Complete problems as well... this leads to a
whole mess of problems being solvable including (I think) factoring
large primes, and other such methods behind encryption...
Again I'm unsure about the factoring large primes problem being in NP
but... :) Oh well
Kelsin
Kelsin wrote:
> Eric Lavigne wrote:
> [...] this leads to a
> whole mess of problems being solvable including (I think) factoring
> large primes, and other such methods behind encryption...
>
> Again I'm unsure about the factoring large primes problem being in NP
> but... :) Oh well
>
> Kelsin
A bit off topic, but is "factoring a large prime" really the right way
to describe what you mean? Be definition, isn't the factorization of
any prime p just 1*p? I just see and hear people talk about factoring
large prime numbers a lot, and almost never hear people talk about
factoring large composite numbers.
Andy Cristina <·············@gmail.com> writes:
> Kelsin wrote:
> > Eric Lavigne wrote:
> > [...] this leads to a whole mess of problems being solvable
> > including (I think) factoring large primes, and other such methods
> > behind encryption...
> > Again I'm unsure about the factoring large primes problem being in
> > NP but... :) Oh well
> > Kelsin
>
> A bit off topic, but is "factoring a large prime" really the right way
> to describe what you mean? Be definition, isn't the factorization of
> any prime p just 1*p? I just see and hear people talk about factoring
> large prime numbers a lot, and almost never hear people talk about
> factoring large composite numbers.
To break RSA and some other asymetric encryption algorithms, it is sufficieny
to factor a *product* of two large prime numbers, each of them having say
512 binary digits. Since many people use encryption, and have heard some
popular explanation of how it works, without quite understanding it, or just
being unprecise (language wise, mathematicly it's of cause plain wrong), they
say things like you have heard.
The complexity class of integer factorization is as far as I know unknown, and
if it could be proved that it is in NP, it would also be in co-NP, which
would prove that NP=co-NP. This means that you would not directly break RSA
if you solve the traveling salesman problem analytically, but it would be
a breakthrough in both mathematics and computer science.
--
Gislet Sælensminde, Phd student, Scientific programmer
Computational biology unit, University of Bergen, Norway
Email: ·····@cbu.uib.no | Complicated is easy, simple is hard.
Andy Cristina <·············@gmail.com> writes:
> Kelsin wrote:
>> Eric Lavigne wrote:
>> [...] this leads to a whole mess of problems being solvable
>> including (I think) factoring large primes, and other such methods
>> behind encryption...
>> Again I'm unsure about the factoring large primes problem being in
>> NP but... :) Oh well
>> Kelsin
>
> A bit off topic, but is "factoring a large prime" really the right way
> to describe what you mean? Be definition, isn't the factorization of
> any prime p just 1*p? I just see and hear people talk about factoring
> large prime numbers a lot, and almost never hear people talk about
> factoring large composite numbers.
Since Bill Gates puts it like this, who are I and you to tell otherwise?
http://mathworld.wolfram.com/PrimeNumber.html
--
__Pascal Bourguignon__ http://www.informatimago.com/
Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay
From: Robert Uhl
Subject: Re: TSP in CL &/or Screamer
Date:
Message-ID: <m3ll4dc9fr.fsf@4dv.net>
"Eric Lavigne" <············@gmail.com> writes:
>
> Internet encryption is analogous to the traveling salesman problem? Or
> breaking all internet encryption is just a problem of similar
> difficulty? If the former I'd love to hear about it.
ISTR from my CS days that all NP-complete problems can be mapped onto
one another, and thus if one solves one then one solves them all. Which
would be Very Interesting.
--
Robert Uhl <http://public.xdi.org/=ruhl>
Nobody ever got fired for choosing Microsoft. Nobody ever looked stupid
for choosing Linux. --Jebediah21
Martin Svenson wrote:
> Maybe this will be of interest:
> http://aima.cs.berkeley.edu/lisp/doc/overview-SEARCH.html#search/domains/tsp.lisp
>
>>From Norvig's book.
>
> // Martin
>
Killer -- looks promising. Many thanks!
Drew Krause schrieb:
> Hello, I've been searching for Lisp code to the Traveling Salesman
> Problem, but it looks like this problem might be a favorite classroom
> assignment -- so no luck.
>
> I'm more interested in using the algorithm than the (undoubtedly worthy)
> exercise of developing it. In particular, I'd like to add a constraint
> that allows me to choose the starting and ending 'cities'.
>
> Any help appreciated. Thanks!
Yes this is indeed a common classroom assignment. I've developed and
used TSP optimizers in CL using genetic algorithms (GA), simulated
annealing (SA) and treshold accepting (TA). The most difficult part
using genetic algorithms here is to make them running non-consing per
generation. SA or TA are easier to implement and works quite well for
the TSP. TA is, in my personal experience, faster and leads to better
results than SA. As mutation operator (in TA and GA) I either reversed
a randomly chosen segment of the path or swapped the positions of two
cities in the whole path (both operations chosen randomly per
generation). For the crossover in GA I used the so called
"order-crossover" which crosses two paths by randomly selecting
segments in both, applying the order constraints in those segments to
the other path and fix up both paths by removing double cities from the
end. I wrote a CAPI user interface around all those stuff so that I
can view the progress of the optimization and to manually choose
different parameters using sliders while the optimization is running.
I hope this is of any help to you,
ciao,
Jochen Schmidt