Re:“American Scientist” Understands Nothing about the Travel...
by orting on Tuesday April 26, 2016 @05:18PM
(#11575724)
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
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!).