1
$\begingroup$

I am reading some properties on the A* search algorithm on Wikipedia, specifically:

"If the heuristic function h is admissible, meaning that it never overestimates the actual minimal cost of reaching the goal, then A* is itself admissible (or optimal) if we do not use a closed set. If a closed set is used, then h must also be monotonic (or consistent) for A* to be optimal."

But I am not sure I understand what a "closed set" refers to. Is it different than an open set / frontier? If so, why? And why do we use a "closed set" as opposed to an "open set" for A*? Is a priority queue a closed set?

| cite | improve this question | |
$\endgroup$
1
$\begingroup$

There are two variants of the A* algorithm:

  • The standard algorithm maintains two sets of vertices. One called the "open set", and the other is called the "closed set".

  • An alternative version maintains just an open set, and doesn't use a closed set. This requires that the heuristic function satisfy some some additional conditions.

See any standard treatment of A* for explanation of how it works and what the closed set is; e.g., A* search.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I never heard that D.W. A* uses a closed set for avoiding re-expanding nodes and that is how it was described in 1968. I checked the link you provide which states that the closed list might be omitted if the heuristic is not monotone, but even in that case we use a closed list and allow re-expanding nodes if they are found with an f-value which is strictly lower than the f-value in the closed set, thus saving a lot of redundant work. There is no point in avoiding using the closed list as it is much smaller than the open list so that it does not make memory usage much worse than the open list. $\endgroup$ – Carlos Linares López Oct 16 '17 at 6:42
  • $\begingroup$ Bullet point 2 seems to be backwards. As I understand it, we require the additional condition (i.e., consistency) in order to be allowed to use a closed set without breaking the optimality of the algorithm (the usage of a closed set makes the algorithm search fewer nodes, not more, so it is for performance, not for correctness). $\endgroup$ – FunctorSalad Jun 9 '19 at 23:57
  • $\begingroup$ OK. You could be right. Unfortunately I don't have time to look into this right now to refresh my memory of A* or why I wrote the above two years ago, or to correct any mistakes. I apologize if there are any inaccuracies in my answer. Perhaps you could write your own answer, that does a better job of answering? I apologize for writing something and then not being available to either defend it or correct it -- I wish I could do better. $\endgroup$ – D.W.♦ Jun 10 '19 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.