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
closed_set = set()
while frontier not empty:
current = frontier.remove_next()
if current == goal_state:
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
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
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).