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

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

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------'|
B2 |  B3   |

And only compare routes if B1 and B3 overlap.

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


More information about the Routing mailing list