News for hackers. Stuff that matters.
Re:“American Scientist” Understands Nothing about the Travel... by vilhelm_s on Tuesday April 26, 2016 @02:03PM (#11574176)
> 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!).

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