Traveling Salesman ProblemDate: 05/24/2001 at 13:37:28 From: Matt Anderson Subject: Traveling Salesman Problem Is there an easy solution to the "Traveling Salesman Problem"? Date: 05/24/2001 at 15:36:15 From: Doctor Shawn Subject: Re: Traveling Salesman Problem Matt, There are easy solutions to some Traveling Salesman Problems (TSPs). In general, however, this is actually very hard. The basic premise behind a TSP (as you probably already know) is to minimize the distance that a salesman has to travel to get to each of a set of cities, visiting each only once. The problem applies to any number of cities, so the easy solutions involve only a few nodes. If there are two cities, there's only one path. In general, there are (n-1)!/2 paths that can be taken, assuming symmetry (that is, the distance from A to B is the same as the distance from B to A). For an explanation of why that is, see: The Travelling Salesman Problem - Robert Dakin http://www.pcug.org.au/~dakin/tsp.htm The number of paths becomes excessively large as n increases. Since there isn't a computer fast enough to figure out all the possible routes, algorithms have to be developed that will return local minima, i.e., solutions that are better than any 'nearby' solutions. These will be pretty good, but can't be guaranteed to be OPTIMAL without figuring out the lengths of all the paths. The TSP is one of a special class of problems known as "NP-complete." Any NP-complete problem could theoretically be solved by converting it to another, equivalent NP-complete problem. So if _any_ NP-complete problem can be solved deterministically (that is, without depending on luck) in polynomial time, then _all_ of them can. However, no one knows whether this is the case. It's an open research question. But even if the TSP could be solved in polynomial time, note that polynomial time, in terms of computer algorithms, is very, very slow. In fact, it's hard to get much worse. (A really good algorithm will run in "n log n" time, meaning that for n additional inputs, it takes n log n times as long to run. An algorithm that runs in polynomial time is just terrible, and will never be implemented if there's any other choice at all.) Some of these terms might be a little foreign to you; check out NP-complete from FOLDOC http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?NP-complete One way to try to get around this is to use less stupid algorithms (brute force lacks elegance). However, as I said earlier, you won't be able to guarantee it's the absolute best solution, although it'll be a pretty good one. For information about these kinds of algorithms, look at: Computer Scientist Solves Old Salesman Problem - ScienceDaily http://www.sciencedaily.com/releases/2001/01/010116075125.htm Research into NP complete problems has gone off on some pretty wild tangents in recent years - quantum computers would be optimal in solving them, as would biological computation. Many advances in DNA computing have been specifically intended to solve this class of problem. For some background on that, review: DNA Computing - (Dr. Leonard Adleman) - Dr. Karron http://www.casi.net/D.BioInformatics1/D.Fall2000ClassPage/DC1/dc.htm So in answer to your question, there is an easy answer only when there aren't enough cities to make the problem interesting. Understanding why the problem is so challenging is half the fun, and there's still research being done on it. Hope that helps. Feel free to write back with any other questions, or if you just want to talk about this some more. - Doctor Shawn, The Math Forum http://mathforum.org/dr.math/ Date: 04/28/2003 at 16:28:21 From: Tony Subject: Minimizing a route My sister runs a route though 31 locations (she delivers catalogs). She starts from her house and goes through each one of the points, finally ending up back at her house at the end. I do not believe the route she runs is the most efficient. What technique do I use to find the most efficient route (fewest miles). Date: 04/28/2003 at 16:45:28 From: Doctor Mitteldorf Subject: Re: Minimizing a route Dear Tony, This is a famous problem in computer science, called the "traveling salesman problem." It resists computational methods. It's roughly true that no one has yet come up with a solution much better than the "brute force" technique of trying all different paths. Trying lots of different possibilities by hand is not such a bad way to go about the problem. Some computer programs take the approach of looking for optimized sub-routes around some subset of the points, then mixing these together in different combinations. Here's a site from the Princeton Mathematics Department devoted entirely to work on the "TSP": Solving Traveling Salesman Problems http://www.math.princeton.edu/tsp/ And here's a site that indexes computer programs that you can download and run that will try to solve the problem. TSP solvers - The Stony Brook Algorithm Repository http://www.cs.sunysb.edu/~algorith/implement/tsp/implement.shtml - Doctor Mitteldorf, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/