CODEWITHSUNDEEP
algorithmpath-findinga-star
Josh
Josh

Reputation: 73

In A* search algorithm what do you check for when looping through the open list?

I'm a bit confused on the next step of what to do after storing the first node. In the wikipedia page about A* it says to ignore the neighbor that is already in the closed set, but if its not then add it to the open set if it is not there and check the g score.

However on this page https://brilliant.org/wiki/a-star-search/, it says to check if the "neighbor has lower g value than current and is in the closed list" then replace the neighbor's g value else if "current g value is lower and this neighbor is in the open list" "then replace the neighbor with the new, lower, g value"

So I'm sort of confused on what to check for. Do I ignore the node if it's already in the closed set or do I need to also check it's g value and replace the neighbor's with it?

What do I do after I have the first node in A*?

Upvotes: 2

Views: 814

Answers (1)

Yakov Galka
Yakov Galka

Reputation: 72479

If we find a neighbor that's in the closed set it means that we already visited it earlier. It means one of the two things:

  1. Its g score is already minimal, so that extra condition on Brilliant will never be executed.

  2. The heuristic function h is not admissible, i.e. it overestimates the actual minimal cost of reaching the goal. In such case the code on Brilliant may find slightly shorter paths, but neither are guaranteed to find the shortest. To find the shortest path using an inadmissible heuristic you would need to "reopen" such nodes. This will cause the algorithm to revisit entire sub-graphs multiple times, which would severely hurt the complexity, and it's not what Brilliant code is doing.

To summarize: the difference between Brilliant and Wikipedia versions is in handling a small corner case that never happens if the A* is given a "correct" (admissible) heuristic function.

So I'm sort of confused on what to check for. Do I ignore the node if it's already in the closed set or do I need to also check it's g value and replace the neighbor's with it?

I'd follow the Wikipedia code and ignore the nodes in closed set entirely.

Upvotes: 2

Related Questions