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

Marcus Wolschon Marcus at Wolschon.biz
Wed Nov 21 16:20:02 GMT 2007


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

Robert (Jamie) Munro schrieb:
> The only problem is I'm not sure if this double tree method actually
> saves anything - are 2 half searches less effort than 1 full search?

Well,
on a multi-core/cpu or multi-threaded-cpu it is less in any case
since you managed to partition the problem into 2 independent
problems that can be solved nearly asynchronously.
In the sequencial case you have at least not made the runtime
worse. (I am not thinking about IO to load map-parts into ram
here.)
Why not make an implementation and compare it? It looks like
your are far enough for a first test.

Marcus
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHRFqyf1hPnk3Z0cQRAn3dAKCkUo07XX6hejol1TMea2DizBb66wCfQSpU
KXkjSvMAWUgnF+uxhh5OChA=
=bvyJ
-----END PGP SIGNATURE-----




More information about the Routing mailing list