Since you decided to nitpick: travelling salesman problem (i.e. finding an minimal route) is a solved problem as in "for decades we have known algorithms to find a minimal path and we teach them to CS grads".
What you refer to is the fact that the computational complexity (i.e. time to finish it) of known algorithms rises exponentially with the size of the problem and exponentially is a code word for "really, really quickly". It just takes too much time to find the minimal path if your graph is big.
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.
Similarly, a car rental company doesn't have to schedule things optimally, they just have to schedule things really good, and that's possible with much less computationally expensive algorithms. The big win is when you go from "no optimization" to "good optimization", not from "good optimization" to "perfect optimization".
> 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.)
To be sure, I wasn't suggesting the problem hadn't been practically solved, and I understand quite well that beyond a certain point, there's very little incentive in improving the solution any further.
In retrospect, I probably should have kept my thoughts to myself, and I probably deserve the downvote or two that I got for not doing so. =)
What you refer to is the fact that the computational complexity (i.e. time to finish it) of known algorithms rises exponentially with the size of the problem and exponentially is a code word for "really, really quickly". It just takes too much time to find the minimal path if your graph is big.
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.
Similarly, a car rental company doesn't have to schedule things optimally, they just have to schedule things really good, and that's possible with much less computationally expensive algorithms. The big win is when you go from "no optimization" to "good optimization", not from "good optimization" to "perfect optimization".