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

[Robert (Jamie) Munro]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Jon Bright wrote:
> 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.

I think that's what I meant - I don't understand your objection above. :-)

Robert (Jamie) Munro
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHQx/Iz+aYVHdncI0RAh10AJ495vOoHfIWgdC24yOYOfL7PtSnkACfaONh
fe5YwWpMj2t/FmM1c3kYFcI=
=G+4l
-----END PGP SIGNATURE-----