On Thu, 27 Jan 2005 00:31:23 GMT, Darin Johnson <***@_usa_._net> wrote:
Post by Darin Johnson
So everybody uses an approximation algorithm.
There is an higher performance (ie, polynomial time) algorithm that
can find a route that is twice the optimal path or better, but even
that probably takes too much time to run for an impatient web user.
So these programs have to take shortcuts. One of these shortcuts
apparently has some interesting worst case behavior.
Weird. Wouldn't it make sense to precalculate route-sections between
significant landmarks along major travel routes (highways, sea and air
routes) etc? Then any request for a route between X and Y would only need
to calculate in real time what the quickest way was to get from X to the
three (or six or whatever) closest pre-mapped landmarks, and ditto from Y,
and then look only at routes that went X-> landmark-close-to-X ->
precalculated shortest path -> landmark-close-to-Y -> Y. Do a quick sort
of the nine or thirty-six resulting route weights (distance, time etc) and
present the best one.
The best part about this is that any computers on this project can spend
their spare processing cycles precalculating finer and finer grids
(setting more and more known landmarks), making subsequent requests faster
Of course, if a major route section goes down for whatever reason,
processing power will probably be diverted to recalculating the immedate
area around it, plus any precalculated routes that pass through that
section. Routes passing through that section which would normally be
handed out as shorted paths based on prior calculations will need to be
checked by a longer algorithm, but all other requests should be OK.
Not to mention that the finer the precalculation grid, the more route
sections will need to be updated per given time period, and the more
recalculation this will involve. Although admittedly, fewer sections will
be part of 'backbone' routes.
Plus, once a route section has been calculated, sanity algorithms could
check that it's working properly, by comparing it to previous data about
routes in the area, knowledge of nearby alternative routes sections, and
checking that the numbers for paths which would normally pass through that
section are now not completely out of whack.
For one thing, I'd like paths between major cities checked after any
recalculation of backbone sections in that city. Routes to the city, from
the city, from A to B via the city, and within the city along paths that
would normally include that segment. If the path lengths increase by a
significant amount (an appropriate percentage), they really need to be
manually checked. Another one is that if shortest path A-B plus shortest
path B-C is shorter than shortest path A-C, there's something really
Even if a section of highway is washed away, there should be backroads
which can connect the two segments, or alternate highways. Travel between
close towns A and B may now be blown out because they have to go via town
C while the A-B highway is repaired, but travel (time, distance) from
faraway-town D to faraway-town E which normally went via the A-B segment
should not be increased by a huge percentage, even if the preferred route
totally changes (switching to the second of two very similarly weighted
interstate highways, for example).
Yay for unstructured rambling!
"Spherical people in frictionless vacuum" - Topi Saavaleinen