4 ms·

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

by Rhapso 16y ago

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

thefool 16y ago
Factorial grows faster than exponential.
- Rhapso 16y ago
  This is my point, which I apparently failed at communicating.
  - thefool 16y ago
    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 http://www.tsp.gatech.edu/index.html if you are interested.
xtacy 16y ago
Using dynamic programming, you can solve the TSP problem in O(n^2 2^n) time with O(n 2^n) space, n = #cities.
baddox 16y ago
I think you mean that there are (cities-1)! total routes. Only the shortest one(s) are solutions.