How to avoid loops/cycles in iterative deepening with linear space?

Question

Breadth first graph search adds states that have already been visited to an explored set to avoid getting stuck in loops and cycles. This is fine since breadth first search needs exponential space to keep all the nodes in memory.

One of the main reasons for using iterative deepening depth first search is to avoid the exponential space requirements. To ensure linear space you can't simply add every visited state to the explored set. How then do you avoid loops in iterative deepening graph search?

My intuition is that you could remove states from the explored set at some point? Or backtrack to the root but that seems more expensive.

Answer 1

The main point of Iterative Deepening is to completely search a potentially infinite (or just really huge) tree with depth first search with storage linear in the maximum you search. To detect cycles, the information that a node has been visited before must be stored somewhere. This requires exponential storage, so there is no non-exponential ID algorithm that prevents searching in cycles.

However, this may not be too bad in practice if the graph is already stored somewhere. The easiest method to do this then is simply to label the 'depth' of every node as encountered by the search, so you can detect when a cycle has been found. (This is essentially the same as depth limited breadth first search, apart from the order.)

But in general, cycle detection requires more storage, or a different algorithm that uses a bit more time. In fact, you can see a very clear time-space trade-off in many cycle detection algorithms.