3 ms·

> It's an NP-complete problem Finding the optimal solution is NP-complete, but approximations are not necessarily so: https://en.wikipedia.org/wiki/Travelling

• MaxBarraclough 6y ago
  Right, I should have made that point more clear. The TSP problem is NP-complete, but it may be possible to come up with an 'incomplete' algorithm that works efficiently for a large subset of the problem space, and it may be possible to find an approximate algorithm that efficiently finds guaranteed near-optimum solutions to all problems. Neither of those two things requires doing the truly difficult (perhaps impossible) work of coming up with a precise, complete, and efficient algorithm to an NP-complete problem.