patternMinor
Why Iterative-Deepening-DFS requires O(b*d) memory?
Viewed 0 times
whydeepeningiterativerequiresdfsmemory
Problem
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
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#37877, answer score: 2
Revisions (0)
No revisions yet.