News for hackers. Stuff that matters.
Re:Who Can Name the Bigger Number? by Rhapso on Thursday July 22, 2010 @08:39PM (#1540018)
"The traveling salesman problem asks for the shortest route connecting a set of cities, given the distances between each pair of cities. The rub is that the number of possible routes grows exponentially with the number of cities."

Is it just me or does the traveling salesman problem have (cities-1)! solutions? thus it is not exponential? and is in fact far more annoying?

Re:Who Can Name the Bigger Number? by baddox on Thursday July 22, 2010 @09:33PM (#1540112)
I think you mean that there are (cities-1)! total routes. Only the shortest one(s) are solutions.
Re:Who Can Name the Bigger Number? by thefool on Thursday July 22, 2010 @09:09PM (#1540072)
Factorial grows faster than exponential.
Re:Who Can Name the Bigger Number? by Rhapso on Thursday July 22, 2010 @09:17PM (#1540086)
This is my point, which I apparently failed at communicating.
Re:Who Can Name the Bigger Number? by thefool on Friday July 23, 2010 @12:49PM (#1541691)
Oops, I just failed at reading.

As the person below answered, there are less naive ways of doing it. Check out: http://www.tsp.gatech.edu/index.html if you are interested.

Re:Who Can Name the Bigger Number? by xtacy on Thursday July 22, 2010 @09:19PM (#1540093)
Using dynamic programming, you can solve the TSP problem in O(n^2 2^n) time with O(n 2^n) space, n = #cities.