3 ms·

>while a computer would take weeks or until the heat death of the universe to do it better. I don't buy this, approximation algorithms are an entire field of C

• hinkley 8mo ago
  Approximations are often good enough, and even annealing tended to give you a better answer if you were willing to wait. Exhaustive search is NP. But part of TSP is that once you have a good answer, you can backtrack on a larger number of bad ones. So there is value to doing both. And for some geometries, Djikstra and friends give you bounds on what the shortest path can be, within a factor of two, so you can start to carve out the problem space even before you’ve found a decent one.