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

Andreas Leupin a.leupin at hispeed.ch
Tue Nov 20 21:28:47 GMT 2007


Hi Jon,
you are right in this point - sorry , I did not check this good  
enough...

...but two points still remain IMHO:
- IMHO it is necessary to use the ends of road-segments as the end- 
points of a route instead of the usually uses nodes - otherwise it is  
quite cumbersome to take into account the turn restrictions in a node...
- I would not store the entire routes, but write only the cost (in my  
case to the destination) to the ends of road segments - otherwise I  
may end in a memory overflow because of the redundancy of information  
by storing entire routes. It is quite easy to get a route in a second  
step then by a "forward" calculation.

Regards
Andreas

Am 20.11.2007 um 22:09 schrieb 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
>
>
> _______________________________________________
> Routing mailing list
> 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



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20071120/bc89bdde/attachment.html>


More information about the Routing mailing list