> What I meant, however, is that the problem has been solved in practice. When you ask Google how to drive from SF to NY, it'll give pretty good answer in milliseconds. Is it an optimal answer? It might be, it might be not, but it's a very good answer. Getting slightly better answer is not worth the computational time because it won't make a difference in practice in your trip.
That's not the traveling salesman problem, it's the shortest path problem, for which polynomial-time algorithms are well-known and taught to first-year computer-science students. (To be fair, driving directions do require coming up with good edge weights on the graph composed of the American highway system, but once you've got weights, you can run Dijkstra's algorithm and you're done. That's probably not how GMaps driving directions work, but the point is that driving directions are not TSP.)
That's not the traveling salesman problem, it's the shortest path problem, for which polynomial-time algorithms are well-known and taught to first-year computer-science students. (To be fair, driving directions do require coming up with good edge weights on the graph composed of the American highway system, but once you've got weights, you can run Dijkstra's algorithm and you're done. That's probably not how GMaps driving directions work, but the point is that driving directions are not TSP.)