#### Archived

This topic is now archived and is closed to further replies.

# A* Problem

This topic is 5532 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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?

##### Share on other sites
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).

##### Share on other sites
So in other words, I DO need to check if the new path is shorter?

yes

##### Share on other sites
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]

Fup? Anyone?

C''mon, someone?

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 15
• 13
• 9
• 12
• 10
• ### Forum Statistics

• Total Topics
631444
• Total Posts
3000099
×