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

Stefan de Konink skinkie at xs4all.nl
Tue Nov 20 16:30:01 GMT 2007


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

Robert (Jamie) Munro schreef:
> 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.

A* is best first, so why would you think the recursion starts?


Next to this, if you start on the end of the route, you need to walk
as-if you are walking the inverse direction. This could get pretty
critical :)



Stefan
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHQwuJYH1+F2Rqwn0RCnXHAJ0YfQrCEad/HI9mpvdkrEyQeT3dYwCeKFP0
4qJCj7V0dpMW0eARcMLuPmA=
=dTJC
-----END PGP SIGNATURE-----




More information about the Routing mailing list