-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 David Lynch wrote: > On Fri, Oct 10, 2008 at 12:32, flo Detig <[EMAIL PROTECTED]> wrote: >> ps: some random thoughts: >> What about even more layers? >> In case of greedy (dijkstra-/a*-style) BFS you could start 'searching' >> until the first higher-layer-node appears, for instance a >> residential-junction. >> After that stay on that layer and only examine 'arcs' to other junctions >> until you reach the first 'secondary-layer-junction', after which you >> can ignore >> junctions to residential (lower-level) streets and move on in bigger steps. >> Once you arrive at the motorway-level you search on that layer / graph >> that solely consists of arcs between 'motorway-junctions' (german >> Autobahnkreuz).. >> (could be implemented by adding an integer for layer to the nodes table >> and computing shortest paths between neighbouring nodes in each layer >> resulting in a edges-/arcs-/pgrouting-table with source-target-cost) >> But how get 'down' again to find the final destination node? > > I'm working on testing an idea that works backwards from the > destination and forwards from the origin at the same time and stops > when they intersect each other. That sounds like it would be a > solution to your problem.
http://en.wikipedia.org/wiki/Bidirectional_search I also suggested a similar idea about a year ago: http://lists.openstreetmap.org/pipermail/routing/2007-November/000106.html Robert (Jamie) Munro -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.8 (Darwin) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iEYEARECAAYFAkjx8c4ACgkQz+aYVHdncI0upQCfeExjg9PQOLnDLJDF+Jpb5Bsv BmMAnAvsmsnigtCaYPNi6NjIS+xMztxP =htkr -----END PGP SIGNATURE----- _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
