<i>If you really want the single best solution, you&#x27;re stuck with checking all N! solutions.</i><p>Agree with lotharbot here. You are as stuck with checking all N! solutions as a sorting algorithm would be. A <i>good</i> TSP algorithm won&#x27;t, and nor will a sorting algorithm.<p>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 <i>not</i> enumerate N! solutions, and actually a lot fewer.<p>The tricky part is that branch-and-bound and branch-and-cut algorithms (such as the one developed by Cook et al.) are <i>implicit enumeration</i> schemes, in that are proven to obtain the best solution of the N! without actually visiting all of them.