Understanding the Travelling Salesman Problem
Category Corrections
Bookmark :
Another widely-known blog posits that when the "Lotus knows" bus does its tour, it's a travelling salesman problem. The first statement is "Not crossing the continent twice is a quick win." But this shows a fundamental misunderstanding of the travelling salesman problem, and that is that you must START and END from the same point.
Rudimentary geometry tells us that the shortest distance between two points is a straight line, so therefore the optimal solution to any travelling salesman problem is a straight line from the origin point to the most distant point and back again. If the requirement were as simple as NY to LA, you'd go NY - LA - NY as a straight line, and that would be it. (the advance physicists and sf-fans among us will point out that the shortest distance between two points is zero. Well, if you can bend space sufficiently, you're right, and when you achieve that, please let me know)
But you'll notice that even the optimal route must cross the continent twice. That's because you have to end where you began. Even with the simplicity of a straight line, the very definition of the problem indicates that the solution is => furthest distance x 2.
Of course, the germane point is: is there a faster route for the bus to take? And the answer is "probably." As you'll discover in any advanced travelling salesman challenge, not all distances are equal. Distances that can be covered during times that would otherwise be useless are cheaper. Thus, a bus that travels from Milwaukee to Silicon Valley over the weekend is taking advantage of the fact that weekend days are better spent moving rather than meeting with people who have classes or jobs. It doesn't help you to arrive at a destination on Saturday when all you can do to be effective is wait around until Monday.
These calculations aren't rocket science. But they aren't trivial either. So I leave you with Wikipedia's description of the travelling salesman problem: "...it is assumed that there is no efficient algorithm for solving TSPs. In other words, it is likely that the worst case running time for any algorithm for TSP increases exponentially with the number of cities, so even some instances with only hundreds of cities will take many CPU years to solve exactly."
If this is the best we can invent to complain about, clearly we're on the right track.
Bookmark :
Another widely-known blog posits that when the "Lotus knows" bus does its tour, it's a travelling salesman problem. The first statement is "Not crossing the continent twice is a quick win." But this shows a fundamental misunderstanding of the travelling salesman problem, and that is that you must START and END from the same point.
Rudimentary geometry tells us that the shortest distance between two points is a straight line, so therefore the optimal solution to any travelling salesman problem is a straight line from the origin point to the most distant point and back again. If the requirement were as simple as NY to LA, you'd go NY - LA - NY as a straight line, and that would be it. (the advance physicists and sf-fans among us will point out that the shortest distance between two points is zero. Well, if you can bend space sufficiently, you're right, and when you achieve that, please let me know)
But you'll notice that even the optimal route must cross the continent twice. That's because you have to end where you began. Even with the simplicity of a straight line, the very definition of the problem indicates that the solution is => furthest distance x 2.
Of course, the germane point is: is there a faster route for the bus to take? And the answer is "probably." As you'll discover in any advanced travelling salesman challenge, not all distances are equal. Distances that can be covered during times that would otherwise be useless are cheaper. Thus, a bus that travels from Milwaukee to Silicon Valley over the weekend is taking advantage of the fact that weekend days are better spent moving rather than meeting with people who have classes or jobs. It doesn't help you to arrive at a destination on Saturday when all you can do to be effective is wait around until Monday.
These calculations aren't rocket science. But they aren't trivial either. So I leave you with Wikipedia's description of the travelling salesman problem: "...it is assumed that there is no efficient algorithm for solving TSPs. In other words, it is likely that the worst case running time for any algorithm for TSP increases exponentially with the number of cities, so even some instances with only hundreds of cities will take many CPU years to solve exactly."
If this is the best we can invent to complain about, clearly we're on the right track.
