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! solu

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.