Data structure for A*'s "open" set

Question

I'm looking at Wikipedia's pseudocode implementation of A* and found myself wondering about what they call openSet. That is, the neighbours we've seen, but not yet analyzed.

The first part of the outer loop reads:

 current := the node in openSet having the lowest fScore[] value

And this makes sense to me, as I intuitively think of openSet as a heap. So we just pop() and get whatever's most interesting to look at next.

But when looping through the neighbours in the inner loop, this happens:

 if neighbor not in openSet // Discover a new node
                openSet.Add(neighbor)

And obviously, that's not going to go well with a heap. So what I'm wondering is this:

How is this contains() check meant to be carried out? Am I supposed to use something like an AVL tree to get logarithmic performance on both lookup and pop?

Would it make sense to keep a separate hashset to keep track?

Or can I altogether ignore this step?

What would be most effecient?

Answer 1

I think I never heard the term "Open Set" as we usually call it "OPEN list" (and by convention we use upper-case letters). I mention this to highlight the fact that this structure is closer to a list than a set indeed ---thought sets might be used as well, see below.

Anyway, your understanding of the purpose of the OPEN list is perfect. It should contain all nodes generated that are awaiting for expansion, in contraposition to the so-called CLOSED list that contains all nodes that have been already expanded.

There are many different implementations of the OPEN list. For a good review of different ways to implement it, see Chapter 3 of Stefan Edelkamp, Stefan Schroedl Heuristic Search: Theory and Applications, Morgan Kaufmann 2011. In the following I'm just describing three typical alternatives:

Plain open list

The first alternative consists simply of using a list which sorts nodes in ascending order of their $f$-value. Extracting nodes from the list is done in $O(1)$ as it just suffices to take the first item from the list. Inserting is a little bit more difficult. The best would consist of creating a small OPEN list with the descendants of a node that has just been expanded and to sort it in ascending order of their $f$-values. Next, merge this sort list with the global OPEN list. The operation has a cost which is logarithmic in the size of the global OPEN list, but be aware that its size grows exponentially.

Bucketed open list

If the $f$-values of all nodes are known to be discrete and also to be bounded by a constant $B$, then create an array with $(B+1)$ locations, each one pointing to one different list. This ensures that inserting nodes in the OPEN list takes only $O(1)$: given a node with an $f$-value equal to $x$, just add it to the tail of the list pointed to by location OPEN[x]. Extracting is a little bit more difficult, but still very easy. You have to keep track of the lower non-empty index $x$, min x. When popping a node return the first node in the list pointed to by OPEN[min x]. Clearly, this requires some maintanenance: first, when removing all nodes with an $f$-value equal to min x, it is necessary to update this lower bound; secondly, if a node with an $f$-value strictly less than the current min x is inserted, min x has to be updated as well.

Using sets

A$^*$ might additionally require to perform searches in the OPEN list. Strictly speaking, this is not required and the only purpose for doing it is to save some memory ---which anyway will grow exponentially. Note please that this will not avoid redundant expansions, as the CLOSED list already serves specifically to that purpose (in a nutshell: before the expansion of any node verify it is not in the CLOSED list; if so, skip the current expansion; otherwise, expand it and insert it into CLOSED) so I do not think it is really common practice to avoid the insertion of nodes in OPEN that are already in OPEN.

Anyway, if you are interested in saving some additional memory at the expense of investing some additional CPU running time, create a set with the current contents of the OPEN list (implemented in either way) and use it only for performing searches. Yeap, you might be thinking that you are then using twice the memory required by A$^*$ but be aware that the memory consumption of this algorithm is exponential in the depth of the paths generated, so that multiplying the memory usage by a low constant (such as two) will not prevent your algorithm from finding solutions that otherwise could have been found.

Hope this helps,

Answer 2

First of all, it makes sense to implement the gScore in the Wikipedia's pseudocode as a hash table.

Next, considering an arbitrary node $v \in V$, it may have three "states":

1. It is in the open list,
2. It is in the closed list,
3. It is in neither open nor closed lists.

Also, note that the key set of gScore is exactly all the nodes in open and closed lists.

Now, you can implement

neighbor not in openSet

as

neighbor not mapped in gScore

Why this works?

Well, if we reached that very test, it means that it is not in the closed list, which implies that neighbor is in the open list or none of the lists. Since gScore contains all open nodes, neighbor is in the open list only if it is in the gScore.

Hope that helps.