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

Stefan de Konink skinkie at xs4all.nl
Tue Nov 20 17:33:26 GMT 2007


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

Marcus Wolschon schreef:
> 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.

I guess you are right about this. But this will imply multiple graphs
isn't it? Or can this be solved in a better way?

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

I guess you could keep a memory of paths with for each added node
compare if the node is part of any other graph. But this will get rather
expensive for larger routes.

What one could do is work with some sort of bounding box:

             | B1
             o----
            /
- -----------o
- ---o------'|
B2 |  B3   |


And only compare routes if B1 and B3 overlap.



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

iD8DBQFHQxpmYH1+F2Rqwn0RCvSeAJ4gxrCSZ4fr43Za6Iw9I77kh6KruQCgiTMM
MhpN936xbHEgbHVWhaUzVtU=
=4vJo
-----END PGP SIGNATURE-----




More information about the Routing mailing list