others (#15) - heuristic function i A* and Shooting Star (#276) - Message List
Hi!
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
Paul,
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.
daniel06/18/09 09:21:29 (17 months ago)-
Message #974
Hi!
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 ?
paweluz06/19/09 00:10:15 (17 months ago)-
Message #975
Hi Pail,
In A* we are using something similar to Manhattan function (|Dx|+|Dy|)/2 http://pgrouting.postlbs.org/browser/trunk/core/src/astar_boost_wrapper.cpp#L75
There you'll see other attempts commented out.
We tried different heuristic function and for some reason (I don't remember now) decided that for a common road network this function is OK. Probably, it was historical reason.
In Shooting* we are using Euclidian distance. http://pgrouting.postlbs.org/browser/trunk/core/src/shooting_star_boost_wrapper.cpp#L100
anton06/19/09 09:07:15 (17 months ago)
-
-
