others (#15) - heuristic function i A* and Shooting Star (#276) - Message List

heuristic function i A* and Shooting Star


Does anyone know, what heuristic function is used in A* and Shooting Star algorithm in pgRouting. I was trying to find it on the Internet, but I could not find any information. I know that the cost is:

cost(s,e)= g(start, v) + h(v, end)

but I do not know what is h function. I find some information that it may be a distance on straight line, form one vertex to another. But then it may use different approaches to identify distance:

- Euclidean distance > Sqrt(Dx²+Dy²+Dz²) ;
- Manhattan distance > |Dx|+|Dy|+|Dz| ;
- Maximum distance > Max(|Dx|, |Dy|, |Dz|).

I found this in  http://matthewpulis.info/thesis.pdf

Can anyone please help me ?

P.S. Sorry for my poor English :)

  • Message #973


    Basically you're right. A* and Shooting* are "goal-oriented" ... not sure this is the correct term, maybe Anton will correct me.
    This means that when the algorithm needs to choose the next point, it not only takes into account the cost to get there but also the distance of the possible next points to visit to the end point.
    So it might prefer a point closer to the final point even if the cost to get there is higher.

    The second cost (h), that takes into account the distance to the end point, is the heuristic component. There are different ways you can get that distance as you already wrote. You can change this and compile pgRouting again. You can also define how "strong" this heuristic component should be.

    PS: Because the performance improvement of the heuristic algorithms is quite low anyway, I'm not sure you can really see a difference in how you calculate your distance.

    • Message #974


      Thanks a lot for your reply, but I actually didn't get any answer :) I am not the developer, I am just a user, and I would like to know what heuristic is used in A* and Shooting Star. I used it in my application, and I am writing a master thesis about it. So I am guessing it is distance from the current point to the last point, on straight lint... right ?