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

[Jon Bright]

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