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

Marcus Wolschon Marcus at Wolschon.biz
Tue Nov 20 17:07:50 GMT 2007


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

Stefan de Konink schrieb:
> 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?
> 
> 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 :)

Actually walking from the end to the start is not uncommon,
since you can have a moving start-point while the calculation
is running and still get pretty good results. Without starting
all over and never finishing since the starting-point is constantly
moving.

However you cannot "meet in the middle" because "the middle" is
no exact location that you can use for the heuristic empoyed.

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

iD8DBQFHQxRlf1hPnk3Z0cQRAgBdAKC+L4SntWYrvihgYDflIvCR4H20ZwCdHP+3
jFywE+4R/bJiYI1hNHAqha0=
=VvbV
-----END PGP SIGNATURE-----




More information about the Routing mailing list