The travelling salesman problem

[GameSnake]

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?"


 

[Sidoh]

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.

[Ender]

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.

[Sidoh]

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.

[iago]

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.

[Rule]

Thanks for bringing this up GameSnake.  It made me go and learn some graph theory.

[iago]

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!

[iago]

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