Understanding the Travelling Salesman Problem
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.
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.
Comments
Of course, that would drive costs up, but that was not part of the original premise as describe.
Posted by David Gursky At 11:32:43 AM On 09/25/2009 |
Make sure the Solar panels are installed properly, it's gonna need a lot of juice to get across the country this way.
Sadly the bus is not making it to Florida.
Posted by Keith Brooks At 09:20:47 AM On 09/25/2009 |
Posted by Charles Robinson At 09:20:39 AM On 09/25/2009 |
@5 - huh?
Posted by Nathan T. Freeman At 09:59:16 AM On 09/25/2009 |
Posted by Dan Sickles At 11:54:33 PM On 09/24/2009 |
Posted by Nelson Morris At 07:44:22 AM On 09/25/2009 |
/Jesper
Posted by Jesper Kiaer At 07:42:37 AM On 09/25/2009 |
Posted by Gregor Liddell At 07:17:56 AM On 10/01/2009 |
Posted by Chris Toohey At 03:31:43 PM On 09/25/2009 |
Posted by indirmeden film izle At 08:02:00 AM On 01/25/2010 |