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

Robert (Jamie) Munro rjmunro at arjam.net
Wed Nov 21 14:53:51 GMT 2007

Hash: SHA1

Andreas Leupin wrote:
>> Am 20.11.2007 um 17:24 schrieb Robert (Jamie) Munro:
>> 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?

> I think, that in principle it should work to do a A*-search from both
> directions, but it is not trivial to define the condition, when the
> iteration can be ended - as a first gess I would say, that it should be
> a good criterion, if two routes meet and it has been confirmed, that
> there is no shorter route to the meeting point from the start as well as
> from the destination. This is fullfilled for the meeting point for
> which,  the routes from start and destination go one node farther than
> to the  meeting point itself

Having thought this through a bit more, I think that what you do is when
you reach a node from one side which you have already got to from the
other side, you treat the total time as a perfect heuristic estimate,
and continue to try routes that look like they may take less time.

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?

AFAICS, the answer may depend on how good the heuristic is. If the
heuristic is rubbish "it takes 0 seconds", then A* degrades to Dijkstra,
in which case it is clearly worth it, hence the "double-tree Dijkstra"
being in the textbooks.

Robert (Jamie) Munro

Ps. Please note that I intended this as a purely theoretical algorithms
thread, I'm not saying that the performance of any particular existing
product is bad and needs this to fix it, or that this is better than
pgrouting, or that we don't need to write algorithms in C or anything
else. :-)
Version: GnuPG v1.4.6 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org


More information about the Routing mailing list