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. -- Regards, Giridhar
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
On 12/21/2011 2:53 PM, 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.
Wait, I'm confused. Is your threshold t a cutoff distance? So what to you want to happen when you get to "t", stop the search? On input, do you specify the destination node? If there is no destination node then it is dijkstra, the distance is the current cost to get to any given node as you explore the graph, ie the sum of the costs on the predecessors. And all you are doing is getting the path from the start node to all nodes in the graph where the path length is less then "t". If this is your case, then one way to handle this in Boost is to create a visitor and check the path length as each node is explored and if it is greater than "t" do not node add any outbound links/nodes to the queue. -Steve
On 12/21/2011 09:08 PM, Stephen Woodbridge wrote:
If this is your case, then one way to handle this in Boost is to create a visitor and check the path length as each node is explored and if it is greater than "t" do not node add any outbound links/nodes to the queue.
Hi, I'm curious on how this would be done. I've tried to do it some time ago but couldn't figure how to use the DijsktraVisitor to achieve it. http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/DijkstraVisitor.html So I've defined a "function_property_map" which allows me to have a function as weight on my graph and in that cost function I can return std::numeric_limits<double>::infinity() when I want to stop the exploration on that path. -- Maxime
On Thu, 22 Dec 2011, Maxime van Noppen wrote:
On 12/21/2011 09:08 PM, Stephen Woodbridge wrote:
If this is your case, then one way to handle this in Boost is to create a visitor and check the path length as each node is explored and if it is greater than "t" do not node add any outbound links/nodes to the queue.
Hi,
I'm curious on how this would be done. I've tried to do it some time ago but couldn't figure how to use the DijsktraVisitor to achieve it.
http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/DijkstraVisitor.html
So I've defined a "function_property_map" which allows me to have a function as weight on my graph and in that cost function I can return std::numeric_limits<double>::infinity() when I want to stop the exploration on that path.
Instead, you can throw an exception from your visitor whenever a vertex is visited whose cost is more than your threshold; in Dijksta's algorithm, vertices are explored in increasing order of cost. -- Jeremiah Willcock
on Wed Dec 21 2011, giridhar
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.
Doesn't sound like it. The heuristic function in A* has to be an /underestimate/ of the remaining distance to the goal. Merely knowing that you don't want to consider any paths more costly/longer than t doesn't lead in any obvious way to an underestimate. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
participants (5)
-
Dave Abrahams -
giridhar -
Jeremiah Willcock -
Maxime van Noppen -
Stephen Woodbridge