Clan x86
General Forums => Academic / School => Math and Other Problems => Topic started by: GameSnake on August 01, 2007, 02:30:42 pm
-
So recently I read about a math problem that is pretty hard to solve, the traveling salesman problem or "TSP" is classified as NP-Hard.. I was just wondering what everyone thinks about it? You could assume your traveling to 5 cities consistently and need to know the shortest (and most cost effective) route.
"If a salesman starts at point A, and if the distances between every pair of points are known, what is the shortest route which visits all points and returns to point A?"
(http://en.wikipedia.org/wiki/Image:Salesman.PNG)
-
I'm not sure what you're asking... I think you're just trying to sound smart.
The traveling salesman problem is pretty old and it's definitely well known. It's not really a "math problem" either. It's a classic computer science problem.
-
It can certainly be thought of as a math problem. I haven't read much about it or thought much about it and for now I'm refraining from looking at any kind of algorithm or solution (not that I plan on working on it or anything right now -- maybe just thinking about it). But a shortcut to discerning the complexity of the problem (for humans at least) is by recasting it as a graph theory problem, in which you must find a Hamiltonian cycle in a weighted graph. Unlike the more amenable Eulerian paths, Hamiltonian paths do not have a complete theory associated with them. This alone shows the complexity of the problem. The sufficient conditions discovered for Hamiltonian paths/cycles are very weak, e.g.: A graph with v vertices has a Hamiltonian cycle if each vertex has degree of at least v/2. This condition is weak because it forces such an uncommon situation.
Anyways, kinda cool that you brought it up because I've been doing a lot of graph theory lately.
-
It's not feasible to solve an even minimally complex instance of this problem mathematically. It's a computer science problem because the only known algorithm is to try all possible routes. That's why it's still around... even modern computers fail to solve this in a reasonable amount of time after a reasonably small number of nodes are added.
-
It's a computer science problem because the only known algorithm is to try all possible routes.
I am pretty sure there are other ways to solve it, just not in polynomial time (which is the definition of NP-hard -- problems that aren't solvable in polynomial time and also aren't NP-complete).
On a side-note, the "best" way to solve this, however, is with an AI-style approach, where you do a search using heuristics. It doesn't always give you the ideal solution, but it can run reasonably quickly.
-
Thanks for bringing this up GameSnake. It made me go and learn some graph theory. :)
-
Nice! Now learn about NP-Complete problems and solve one in polynomial time. If you solve one NP-Complete, you've solved them all since, by definition, they can provably be reduced to each other. If somebody discovers a way, they'll be famous!
-
Apparently, a solution that could solve the traveling salesman problem in quadratic time has been proposed:
http://science.slashdot.org/article.pl?sid=07/08/09/1535231
http://www.opticsexpress.org/abstract.cfm?id=140598