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

[Jon Bright]

Hi Andreas,

Andreas Leupin wrote:
 > However, I think that the A*-algorithm is not ideal because it is
 > absolutely symmetrical around the start/destination - this means that
 > routes leading away from the destination are equal than those leading
 > into the direction of the destination.

I skimmed over the PDF at

http://www.leupinfo.ch/pdf/OpenGPScout_YP.pdf

As far as I can make out, the routing algorithm you're describing /is/ 
in fact A* (from the destination to the start).  The straight-line 
distance you describe is (one possible) heuristic as used by A*.  To 
quote from

http://en.wikipedia.org/wiki/A*_search_algorithm

"The priority assigned to a path x is determined by the function f(x) = 
g(x) + h(x)."

g(x) here is the distance travelled, while h(x) is a heuristic for the 
distance still to travel - in your case the straight-line distance.

Have I misunderstood?

--
Jon

Andreas Leupin wrote:
> However, I think that the A*-algorithm is not ideal because it is 
> absolutely symmetrical around the start/destination - this means that 
> routes leading away from the destination are equal than those leading 
> into the direction of the destination. On www.leupinfo.ch/OpenGPScout 
> <http://www.leupinfo.ch/OpenGPScout> I tried to describe an algorithm, 
> which is very similar to A* but prefers the routes to the direction of 
> the destination...
> Furthermore I prefer to calculate the route from destination to start, 
> because the start-point is constantly changing during the drive, whereas 
> the destination is stable - therefore, I can use the calculations 
> already done, when I leave the precalculated route during my drive...
> Regards
> Andreas
> 
> Am 20.11.2007 um 17:24 schrieb Robert (Jamie) Munro:
> 
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> 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?
>>
>> AFAICS, this is likely to be quicker than a normal A-star because the
>> recursion will be less broad. I'm not 100% sure though.
>>
>> Robert (Jamie) Munro
>> -----BEGIN PGP SIGNATURE-----
>> Version: GnuPG v1.4.6 (Darwin)
>> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>>
>> iD8DBQFHQwpAz+aYVHdncI0RAvhqAJ9WQlNWFO47CTiOc61MgwgXrgoDuQCgn9+Y
>> 1MLVeZXctjbxXefe+p1cp7k=
>> =BS9q
>> -----END PGP SIGNATURE-----
>>
>> _______________________________________________
>> Routing mailing list
>> Routing at openstreetmap.org <mailto:Routing at openstreetmap.org>
>> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
> 
> Andreas Leupin
> Kretzgasse 2
> CH-5416-Kirchdorf
> Tel. P [+41](0)56 282 07 40
>        G [+41](0)56 310 39 32
> a.leupin at hispeed.ch <mailto:a.leupin at hispeed.ch>
> 
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing