How do I keep track of already visited states in breadth-first search?

Question

I was trying to implement the breadth-first search (BFS) algorithm for the sliding blocks puzzle (number type). Now, the main thing I noticed is that, if you have a $4 \times 4$ board, the number of states can be as large as $16!$, so I cannot enumerate all states beforehand.

How do I keep track of already visited states? I am using a class board each class instance contains a unique board pattern and is created by enumerating all possible steps from the current step.

I searched on the net and, apparently, they do not go back to the just-completed previous step, BUT we can go back to the previous step by another route too and then again re-enumerate all steps which have been previously visited.

So, how to keep track of visited states when all the states have not been enumerated already? Comparing already present states to the present step will be costly.

Answer 1

You can use a set (in the mathematical sense of the word, i.e. a collection that cannot contain duplicates) to store states that you have already seen. The operations you'll need to be able to perform on this are:

• inserting elements
• testing if elements are already in there

Pretty much every programming language should already have support for a data structure that can perform both of these operations in constant ($O(1)$) time. For example:

• set in Python
• HashSet in Java

At first glance, it may seem like adding all the states you ever see to a set like this will be expensive memory-wise, but it is not too bad in comparison to the memory you already need for your frontier; if your branching factor is $b$, your frontier will grow by $b - 1$ elements per node that you visit (remove $1$ node from frontier to "visit" it, add $b$ new successors/children), whereas your set will only grow by $1$ extra node per visited node.

In pseudocode, such a set (let's name it closed_set, to be consistent with the pseudocode on wikipedia could be used in a Breadth-First Search as follows:

frontier = First-In-First-Out Queue
frontier.add(initial_state)

closed_set = set()

while frontier not empty:
    current = frontier.remove_next()

    if current == goal_state:
        return something

    for each child in current.generate_children()
        if child not in closed_set:    // This operation should be supported in O(1) time regardless of closed_set's current size
            frontier.add(child)

    closed_set.add(current)    // this should also run in O(1) time

(some variations of this pseudocode might work too, and be more or less efficient depending on the situation; for example, you could also take the closed_set to contain all nodes of which you have already added children to the frontier, and then entirely avoid the generate_children() call if current is already in the closed_set.)

---

What I described above would be the standard way to handle this problem. Intuitively, I suspect a different "solution" could be to always randomize the order of a new list of successor states before adding them to the frontier. This way, you do not avoid the problem of occasionally adding states that you've already previousl expanded to the frontier, but I do think it should significantly reduce the risk of getting stuck in infinite cycles.

Be careful: I do not know of any formal analysis of this solution that proves that it always avoids infinite cycles though. If I try to "run" this through my head, intuitively, I suspect it should kind of work, and it does not require any extra memory. There may be edge cases that I'm not thinking of right now though, so it also simply might not work, the standard solution described above will be a safer bet (at the cost of more memory).

Answer 2

Dennis Soemers' answer is correct: you should use a HashSet or a similar structure to keep track of visited states in BFS Graph Search.

However, it doesn't quite answer your question. You're right, that in the worst case, BFS will then require you to store 16! nodes. Even though the insertion and check times in the set will be O(1), you'll still need an absurd amount of memory.

To fix this, don't use BFS. It's intractable for all but the simplest of problems, because it requires both time and memory that are exponential in the distance to the nearest goal state.

A much more memory-efficient algorithm is iterative deepening. It has all the desirable properties of BFS, but uses only O(n) memory, where n is the number of moves to reach the nearest solution. It might still take a while, but you'll hit memory limits long before CPU-related limits.

Better still, develop a domain specific heuristic, and use A* search. This should require you to examine only a very small number of nodes, and allow the search to complete in something much closer to linear time.

Answer 3

While the answers given are generally true, a BFS in the 15-puzzle is not only quite feasible, it was done in 2005! The paper that describes the approach can be found here:

http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

A few key points:

• In order to do this, external memory was required - that is the BFS used the hard drive for storage instead of RAM.
• There are actually only 15!/2 states, since the state space has two mutually unreachable components.
• This works in the sliding tile puzzle because the state spaces grows really slowly from level to level. This means that the total memory required for any level is far smaller than the full size of the state space. (This contrasts with a state space like Rubik's Cube, where the state space grows much more quickly.)
• Because the sliding-tile puzzle is undirected, you only have to worry about duplicates in the current or previous layer. In a directed space you may generate duplicates in any previous layer of the search which makes things much more complicated.
• In the original work by Korf (linked above) they didn't actually store the result of the search - the search just computed how many states were at each level. If you want to store the first results you need something like WMBFS (http://www.cs.du.edu/~sturtevant/papers/bfs_min_write.pdf)
• There are three primary approaches to comparing states from the previous layers when states are stored on disk.
  • The first is sorting-based. If you sort two files of successors, you can scan them in linear order to find duplicates.
  • The second is hash-based. If you use a hash function to group successors into files, you can load files which are smaller than the full state space to check for duplicates. (Note that there are two hash functions here -- one to send a state to a file, and one to differentiate states within that file.)
  • The third is structured duplicate detection. This is a form of hash-based detection, but it is done in a way that duplicates can be checked immediately when they are generated instead of after they have all been generated.

There is a lot more to be said here, but the paper(s) above give a lot more details.

Answer 4

Ironically the answer is "use whatever system you want." A hashSet is a good idea. However, it turns out that your concerns over memory usage are unfounded. BFS is so bad at these sorts of problems, that it resolves this issue for you.

Consider that your BFS requires you to keep a stack of unprocessed states. As you progress into the puzzle, the states you deal with become more and more different, so you're likely to see that each ply of your BFS multiplies the number of states to look at by roughly 3.

This means that, when you're processing the last ply of your BFS, you have to have at least 16!/3 states in memory. Whatever approach you used to make sure that fit in memory will be sufficient to ensure your previously-visited list fits in memory as well.

As others have pointed out, this is not the best algorithm to use. Use an algorithm which is a better fit for the problem.

Answer 5

Approaches to the Game

It is true that the board has $16!$ possible states. It is also true that using a hash set is what students learn in a first year algorithms courses to avoid redundancy and endless looping when searching a graph that may contain graph cycles.

However, those trivial facts are not pertinent if the goal is to complete the puzzle in the fewest computing cycles. Breadth first search isn't a practical way to complete an orthogonal move puzzle. The very high cost of a breadth first search would only be necessary if number of moves is of paramount importance for some reason.

Sub-sequence Descent

Most of the vertices representing states will never be visited, and each state that is visited can have between two and four outgoing edges. Each block has an initial position and a final position and the board is symmetric. The greatest freedom of choice exists when the open space is one of the four middle positions. The least is when the open space is one of the four corner positions.

A reasonable disparity (error) function is simply the sum of all x disparities plus the sum of all y disparities and a number heuristically representing which of the three levels of freedom of movement exists because of the resulting placement of the open space (middle, edge, corner).

Although blocks may temporarily move away from their destinations to support a strategy toward completion requiring a sequence of moves, there is rarely a case where such a strategy exceeds eight moves, generating, on the average, 5,184 permutations for which the final states can be compared using the disparity function above.

If the empty space and positions of block 1 through 15 are encoded as an array of nibbles, only addition, subtraction, and bit-wise operations are needed, making the algorithm fast. Repeating the eight move brute force strategies can be repeated until disparity falls to zero.

Summary

This algorithm cannot cycle because there is always at least one of the permutations of eight moves that decreases disparity, regardless of the initial state, with the exception of a starting state that is already complete.