Why Iterative-Deepening-DFS requires O(b*d) memory?

Question

After reading about iterative deepening depth-first search on Wikipedia, I could understand that it just limits the depth upto which dfs can go in one iteration/call.

However, I could not understand why it is said that it requires $O(b \times d)$ memory, where $b$ is fan-out of nodes i.e. children and $d$ is max-depth.

Since it is just doing DFS multiple times, it should also only need $O(d)$ memory.

Thinking more, I thought that may be the entire graph can not be put in memory and $O(b\times d)$ is the part of graph required to be kept in memory. But does that make DFS also have $O(b\times d)$ memory requirement ? But even this does not like a good argument, because since during traversal if we are fetching the new nodes from some storage, we can do so also with $O(d)$ memory.

Also the Wikipedia page examples lead me to infer that it does not store visited[node_id] information about the nodes which stores whether node with id node_id is visited till now or not. This made me infer that graph is big.

Edit: After thinking further i think that it is right about $O(b \times d)$, since it is iterative-dfs rather than recursive-dfs. In recursive-dfs we usually take memory used by function call stack for granted. In iterative-dfs, we can find right memory-requirements. Since, now we can not implicitly remember back-tracking, we have to put all children on the stack and hence if we are going to $d$ levels, we need $O(b\times d)$ memory.

Answer 1

Well, one can say that $O(bd)$ is the bound for iterative-deepening depth-first search (DFID). It is not necessarily true that there is a mistake in Wikipedia. In general, every node is expanded and all its $b$ children are generated. Doing so allows for additional strategies, e.g., sorting them. Then a loop traverses all nodes and DFID is invoked recursively on each one. Thus, when a solution is found at depth $d$, $db$ nodes are stored in memory.

However, in many cases you can do as you suggest and generate the children efficiently one at a time. In this particular case we usually say that DFID takes $O(d)$ (instead of $\Theta(d\log b)$): Instead of expanding all nodes you just take the first one and invoke DFID recursively over it. When the search resumes in this particular node we just take the next one. This sort of implementations works as Tom van der Zanden explained but there is no specific need to remember that we are located at the 2nd child or the 5th child. There are two reasons for this:

1. Once the solution is found, the path to it is in the stack ---so you won't get lost, no need to remember which were the specific orderings of the children generated above your current state.
2. A naive implementation might require remembering we considered the $n$-th child to generate the $(n+1)$-th child but some tricks can be used to avoid this specifically. Take for instance the $N$-puzzle. In this case, the descendants can be precomputed in a table (as Richard Korf did in his original implementation of IDA$^*$) and the children are just stored in an array of known length. Then $O(d)$ is feasible just by traversing this array. The same trick can be accomplished in other domains such as the $N$-pancake, the Rubik's cube, Topspin (where it is even easier!) and such ...

As a matter of fact, Richard Korf (who originally devised the idea of DFID) describes the space complexity of DFID in page 100 in the following terms: "since at any given time, it is performing a depth-first search, the space it uses is $O(d)$" Richard E. Korf. Depth-First Iterative-Deepening: An Optimal Admissible Tree Search. Artificial Intelligence Journal, 27(1). 1985. 99--121 This statement assumes that the considerations made above apply in your domain.

However, it might be a good idea indeed to have a look at all descendants before starting to invoke DFID over them (and therefore incurring in a space complexity $O(bd)$), and Alexander Reinefeld considered a good number of ideas based on this observation. See the paper: Alexander Reinefeld. Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA$^*$. IJCAI 1993. 248--253.

Finally, a similar idea (ie., generating only a specific node that satisfies a particular condition) has been tried also in the context of A$^*$. For more information see Meir Goldenberg, Ariel Felner, Nathan Sturtevant, Robert Holte, Jonathan Schaeffer. Optimal-Generation Variants of EPEA$^*$, Proceedings of the Fifth International Symposium on Combinatorial Search, (SoCS-2013), July 2013

Cheers,

Answer 2

You need $\Theta(d \lg b)$ memory in order to store where in the tree you are: a position at depth $d$ in the tree is given by $d$ integers in the range $1\ldots b$ indicating for each branch in the tree which particular child you're looking at.

You could think of it as a set of directions of how to get from the root node to the current child. For example: at the root, take the 2nd child, then take the 5th child of that node, and so on.

When you're doing DFS, you need this information: once you've considered all children of a node at depth $d$, you need to go back to the previous node at depth $d-1$ and consider its next child, but you can only get to its next child by knowing what child you're currently looking at.

It's not clear why Wikipedia says $O(bd)$. Perhaps this is a mistake in the Wikipedia page.