Comment by krackers
13 days ago
>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 CS, if you're OK with an approximate solution I'm sure computers could do that quickly as well.
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.