algorithmsearchgraph-theorypseudocode

Can the A* search algorithm be implemented without a closed list?


The A* search algorithm is usually implemented using an open and a closed list (or other data structures). Recently I read in Wikpedia a pseudocode that makes use only of an open list.


Solution

  • The heuristic function has some properties which can be false or true, including: admissible and consistent.

    If the algorithm puts nodes in a closed list -- marking the last evaluation for that node as final -- then we must assume that the heuristic is consistent. If it is not, we might put nodes in the closed list that could still be reached with a lesser cost. And this may result in a non-optimal path.

    The algorithm provided in the Wikipedia article does not put nodes in a closed list, but always checks if a neighbor of the current node could get a better evaluation, even if it that neighbor had previously been in the open list. The text below the pseudo code explains this:

    Remark: In this pseudocode, if a node is reached by one path, removed from openSet, and subsequently reached by a cheaper path, it will be added to openSet again. This is essential to guarantee that the path returned is optimal if the heuristic function is admissible but not consistent. If the heuristic is consistent, when a node is removed from openSet the path to it is guaranteed to be optimal so the test tentative_gScore < gScore[neighbor] will always fail if the node is reached again.

    You could say that the condition tentative_gScore < gScore[neighbor] plays the role of the closed list check, but is more generic in its application, as now the algorithm will also work for non-consistent heuristic functions.