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

Andreas Leupin a.leupin at hispeed.ch
Tue Nov 20 20:45:54 GMT 2007


I think, that in principle it should work to do a A*-search from both  
directions, but it is not trivial to define the condition, when the  
iteration can be ended - as a first gess I would say, that it should  
be a good criterion, if two routes meet and it has been confirmed,  
that there is no shorter route to the meeting point from the start as  
well as from the destination. This is fullfilled for the meeting  
point for which,  the routes from start and destination go one node  
farther than to the  meeting point itself
Regards
Andreas
Am 20.11.2007 um 17:24 schrieb Robert (Jamie) Munro:

> -----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

Andreas Leupin
Kretzgasse 2
CH-5416-Kirchdorf
Tel. P [+41](0)56 282 07 40
        G [+41](0)56 310 39 32
a.leupin at hispeed.ch



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20071120/08e4255e/attachment.html>


More information about the Routing mailing list