Space Complexity of Ids Algorithm

Question

Hello I try to calculate the space complexity of IDS (Iterative deepening depth-first search) algorithm but I cannot figure out how to do that. I can't really understand how the algorithm visits the nodes of a tree, so that I could calculate how space it needs. Can you help me?

Answer 1

As far as i have understood, IDS works like this: starting with a limit of 0, meaning the depth of the root node in a graph(or your starting point), it performs a Depth First Search until it exhausts the nodes it finds within the sub-graph defined by the limit. It then proceeds by increasing the limit by one, and performing a Depth First Search from the same starting point, but on the now bigger sub-graph defined by the larger limit. This way, IDS manages to combine benefits of DFS with those of BFS(breadth first search). I hope this clears up a few things.

Answer 2

from Wikipedia:

The space complexity of IDDFS is O(bd), where b is the branching factor and d is the depth of shallowest goal. Since iterative deepening visits states multiple times, it may seem wasteful, but it turns out to be not so costly, since in a tree most of the nodes are in the bottom level, so it does not matter much if the upper levels are visited multiple times.[2]