A* Problem
Author
In all the pseudocodes of A* that I have seen, before adding the current node''s neighbors to the open list, the program checks whether the cost of getting there is less than the cost of getting there by a path already taken. For example, if you have visited the node before, but it took longer than it did using this path, you put the new version of the node onto the open list and pop the old one off. However, my friend tells me that this is unnecessary. He says that since A* finds the shortest path to any node anyway, checking to see that the new way is shorter is redundant ''cause it always will be. I''m not so sure. Do you guys have any ideas?
First of all, A* will only find the shortest path to the goal when the heuristic used is admissible (meaning that the heuristic never overestimates the cost to the goal). If the heuristic isn''t admissible, then A* can find a path but it makes no guarantees as to how good the path is.
Next, even if the heuristic is admissible, it has not found the shortest path to a node until it has expanded that node. If a node is still on the open list, there is no way to know if the shortest path to that node has been found. Only when a node is on the closed list do you know you have found the shortest path to it (and even then, I''m not sure if this holds if the heuristic is not monotonic).
Next, even if the heuristic is admissible, it has not found the shortest path to a node until it has expanded that node. If a node is still on the open list, there is no way to know if the shortest path to that node has been found. Only when a node is on the closed list do you know you have found the shortest path to it (and even then, I''m not sure if this holds if the heuristic is not monotonic).
Author
and even then, I'm not sure if this holds if the heuristic is not monotonic.
What is a monotonic heuristic? Also, do I have to check both (open + closed) lists or just one of them? And what's the reasoning behind this?
[edited by - yaroslavd on April 30, 2003 10:33:43 PM]
What is a monotonic heuristic? Also, do I have to check both (open + closed) lists or just one of them? And what's the reasoning behind this?
[edited by - yaroslavd on April 30, 2003 10:33:43 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
