It's possible to cast this problem - which is basically an optimality one, we're looking for the best tour - into a yes-no one also by simply asking:
Can we find a tour with a cost less than x?
By asking this question until we find a tour with a cost x for which the answer is provably no, we have found the optimal tour. This problem can also be proved to be in NP. (It is reducible to the Hamiltonian circuit problem.)
Various heuristics have been developed to find near optimal solutions with efficient algorithms.
One simple approach is the find the minimum spanning tree. One possible tour simple traverses the MST twice. So we can find a tour which is at most twice as long as the optimum tour in polynomial time. Various heuristics can now be applied to reduce this tour, eg by taking shortcuts.
An algorithm due to Christofides can be shown to produce a tour which is no more than 50% longer than the optimal tour.
 | It starts with the MST and singles out all cities which are linked to an odd number of cities. These are linked in pairs by a variant of the procedure used to find compatible room-mates. |
 | This can then be improved by taking shortcuts. |
Another strategy which works well in practice is to divide the "map" into many small regions and to generate the optimum tour by exhaustive search within those small regions. A greedy algorithm can then be used to link the regions. While this algorithm will produce tours as little as 5% longer than the optimum tour in acceptable times, it is still not guaranteed to produce the optimal solution.
