[Routing] [OSM-dev] pre-compute routing

[Robert (Jamie) Munro]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Marcus Wolschon - Wolschon Softwaredesign wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Robert (Jamie) Munro schrieb:
>> I think we only need to store the first one. The second one is the same
>> as the route from that node to the destination. I.e. if the route is
>> A->B->C->D, then we just need to store A->D=B, then lookup B->D=C, then
>> C->D=D.
> 
>> In many, probably most, cases, the next node to go to will be the same
>> no matter which type of route you are taking, so we only need to store
>> different routes for different types of route when they actually differ.
> 
> So you would
> a: still calculate O(N^2) routes (for very very large N)
> and
> b: find the longest-common-subsequence.

Err, no. At worst we need to do a dijkstra-style run for each node to
the edges of the map, and save the entire result. That's still O(N^2)
but no LCS is needed. But that's only a first stab at an algorithm to
populate the tree. I'm sure that we can invent something that populates
a large proportion of the possible routes in a single pass.

It may be possible to make an algorithm that starts with rubbish routes,
and iteratively improves them. For example, after one dijkstra-pass, we
have a route from any node to any node via the starting node. Often this
will be rubbish, but if we were to do several passes from different
parts of the country, they would all cross over, and we may quickly
converge to something usable.

I'm wondering about doing something quad-tile based. I haven't quite
formulated a whole method but it begins with:

Find a quad tile with only a few nodes in it (keep subdividing until you
find the last one with n>1). Iterate out from all of the nodes in the
tile until you reach a point where to get back to any point in the tile
you start by going the same way. From that point on you can treat the
whole quad tile as a single node. There should be a way to work through
the whole graph consolidating it into quad tiles as you go.

Robert (Jamie) Munro
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHAmOjz+aYVHdncI0RAlYzAKCsQ78Djm+yprsZcw76+vTYeZgrigCgjL4N
BcXEFCnZxwr55zPEzAKi7h4=
=P8ZO
-----END PGP SIGNATURE-----