>> There a good chances that they use an approach similar to that one : >> >> Precomputation: >> - Find 100 × 100 points in europe (that means a point every 30km) >> - Compute the distance between all those points and store it >> >> > Every 30km? Choose a popular location close to it .. Not really necessary, as anyway you will compute the shortest path to that point. The goal is only to have a very good distance estimation. Not the path itself. Of course being smart while choosing the points will turn out in a slightly faster solution. Not really a big deal.
And even choosing a 1000×1000grid (a node every 3km) will only consume 4 Mb (you just store a duration for every pair of start-destination). But you will need to run one million times a shortest path algorithm in before hand. > You know what a transition matrix is?? Product of transition matrix?? > The Nth product will give you all paths of lenth N ;-) (close subject: > markov chains) The matrix will contain all 100^2 distances. It's not an adjacency matrix. So you won't compute the paths using the matrix, but a plain old A*. > In modern times 100.000 destinations isn't that much ;-) > 100.000 x 100.000 matrix. Again, you don't pre-compute the paths. You just pre-compute a few distances in order to have a better heuristic and achieve a quasi-linear shortestpath algorithm. You'll have as many destinations as you have nodes in your graph (about 1 million currently in OSM for France). _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
