On Wed, 21 Dec 2011, giridhar wrote:
Hello All,
I have a question about defining A* heuristic. I am trying to implement an algorithm in a paper using BGL. Here authors have used A* Dijkstra's to calculate shortest route with an additional constraint of route length should be no longer than a threshold value t.
I think due to this threshold constraint they are using A* instead of normal Dijkstra's algorithm.
I came to know A* is already there in Boost Graph Library. I just have a basic knowledge about A* algorithm that it finds the shortest route based on the heuristic H.
I tried to look into the example in BGL, but I did not get any hint to define a heuristic. Can anybody give me some hints or some useful links of how can I define a heuristic for this particular scenario of finding the shortest path between nodes that is no longer than threshold t through A* Dijkstra. This would be really helpful for me to proceed further.
The heuristic is something that is application-specific; there is no single heuristic for all graphs. If your graph is something like a road network, there are distance-based heuristics you can use. See http://en.wikipedia.org/wiki/A* and http://en.wikipedia.org/wiki/Admissible_heuristic for more information and examples. If you don't have a heuristic available, Dijkstra's algorithm is likely to be preferable, especially if your graph is not tree-like (many paths converge to a single node). -- Jeremiah Willcock