> 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!).
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!).
"Every subpath of a path of minimum distance is itself of minimum distance."
[0] https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm