[Routing] A-Star meet-in-the-middle
Jon Bright
jon at siliconcircus.com
Tue Nov 20 16:59:29 GMT 2007
Hi,
Robert (Jamie) Munro wrote:
>
> 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?
This doesn't (I think) work. A* might reach a given node X, but it has
no idea whether the route it has found to that node is the shortest
route to that node. So your two A*s might meet at a given node, but
you're still none the wiser about whether that's the shortest route,
because you don't know whether the two routes you have are the shortest
route to the meeting node.
What you should be able to do, though, is to start from source and
destination at the same time and whenever these meet, add the
from-destination routes, reversed, to the end of the from-source routes
which meet that node. One such route has good chances of turning out to
be the shortest - and by working in this way, you'll likely discover
that route more quickly. Worth trying, anyway.
--
Jon Bright
Silicon Circus Ltd.
http://www.siliconcircus.com
More information about the Routing
mailing list