[Routing] A-Star meet-in-the-middle

Brandon Martin-Anderson badhill at gmail.com
Tue Nov 20 18:30:23 GMT 2007


Yeah I think that'd work. A fairly common textbook optimization of the raw
Dijkstra algorithm, the "double-tree Dijkstra", does the same thing. I don't
think there's anything about A* that invalidates the basic approach of
growing a shortest path tree from both the origin and the destination and
stopping when they meet up. There is, however, no easy way to do this with
pgrouting. You'd have to hack it yourself.

-B

On Nov 20, 2007 8:24 AM, Robert (Jamie) Munro <rjmunro at arjam.net> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Is there a reason you can't route by doing 2 A-stars simultaneously, one
> from the start and one from the destination, and stop when the 2 meet?
>
> AFAICS, this is likely to be quicker than a normal A-star because the
> recursion will be less broad. I'm not 100% sure though.
>
> Robert (Jamie) Munro
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.6 (Darwin)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iD8DBQFHQwpAz+aYVHdncI0RAvhqAJ9WQlNWFO47CTiOc61MgwgXrgoDuQCgn9+Y
> 1MLVeZXctjbxXefe+p1cp7k=
> =BS9q
> -----END PGP SIGNATURE-----
>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20071120/ae43aecd/attachment.html>


More information about the Routing mailing list