Hacker News Reader

Comment by bradford | Hacker News Reader

> Nobody compares all N! permutation for sorting, and nobody checks all N! tours when solving a TSP.

Doesn't this depend on what you mean by 'solve'? If you really want the single best solution, you're stuck with checking all N! solutions. If you want a solution which merely works pretty well almost all of the time, then you're right, there are many polynomial time solutions.

I wasn't able to read the Scientific American article that the author ranted against, but if it's discussing TSP from a mathematical standpoint, I wouldn't fault them for discussing the feasibility of checking all N! permutations... that's exactly how it was discussed to me in my introductory computation classes.

View on HN

> "you're stuck with checking all N! solutions"

not quite -- once you have a solution that runs in time X, you no longer need to check any solution that has a sub-component that is known to take longer than time X. So, for example, if you find that going between locations A, C, J, F, P, E, and Q in that order takes longer than your current best whole-map solution, then you no longer have to check any solution of which ACJFPEQ is a subset. You can eliminate whole categories of solutions with a single check, instead of having to test each of them one-by-one.

So, memoization, a basic optimization technique.

Yes, the easiest example of optimization to give was a basic example. There are much better techniques too.

> If you really want the single best solution, you're stuck with checking all N! solutions.

No, you're not. There is an exact dynamic programming algorithm that takes O(n^2 2^n) time, which is exponential but much smaller than O(n!).

It is from Bellman, Held and Karp [0] and has O*(2^n) complexity for both space and time. It is quite simple and based on the idea that

"Every subpath of a path of minimum distance is itself of minimum distance."

[0] https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm

The linked post mentions a previous post [1] where he mentions that proving you have the optimal path doesn't always require N! cost:

> If you have an instance of the TSP of practical interest (i.e. it makes a difference to your life if you solve it or not, and it is really a TSP, not the result of some weird set of set of reductions from some other problem), then I bet you the Concorde program of Bill Cook and others will get you a provably optimal solution in a reasonable amount of time. In fact, I would be really interested in knowing the smallest “real” instance that Concorde cannot solve in, say, one day, on a normal laptop computer.

Note the "provably" before "optimal solution".

1: http://mat.tepper.cmu.edu/blog/?p=6995

If you really want the single best solution, you're stuck with checking all N! solutions.

Agree with lotharbot here. You are as stuck with checking all N! solutions as a sorting algorithm would be. A good TSP algorithm won't, and nor will a sorting algorithm.

Just as sorting has a vast set of solutions, the best of which we can find in guaranteed O(n log n) time, a TSP problem admits an algorithm (branch-and-cut) that does not enumerate N! solutions, and actually a lot fewer.

The tricky part is that branch-and-bound and branch-and-cut algorithms (such as the one developed by Cook et al.) are implicit enumeration schemes, in that are proven to obtain the best solution of the N! without actually visiting all of them.

Reply on news.ycombinator.com