Memory usage in Iterative-Deepening DFS(ID-DFS) and BFS

Question

I am reading a lecture in https://www.ics.uci.edu/~welling/teaching/271fall09/UninformedSearch271f09.pdf

The memory usage in BFS is O(b^d+1), and the memory usage in ID-DFS is O(bd).

There's one thing that I want to check, why ID-DFS does not store all the visited nodes?

The reason I have figure out is that it only needs to store the path and the nodes that it has expanded on the path. For other nodes outside the path that it has visited can be discarded from the tree(free them from memory), because these nodes are not benefit to directing from root to the goal node.

For BFS, because we don't know where the solution is, we can not discard the nodes that we have visited until we have found the solution.

Is above thought correct or wrong?

Notes: To be more precise, in ID-DFS, to the best of my knowledge, when visiting a node, we should generate all legal children of it, say n children, and visit the first child n1. For the second child n2, it will be visited until the limited-depth DFS has done searching n1. That's why the memory usage in ID-DFS is O(bd), branching factor times depth. For some application that it don't need to generate all children when visiting a node, it can just generate the first child; for the second child, it can be generated after searching the n1 and return. For such modification, it only need to store the path, so its memory usage is O(d).

Answer 1

I am assuming this is an introudction to an AI course.

Let us first make sure we are talking about tree search instead of graph search. In tree search you just need a fringe while you will need both a fringe and a close set in graph search. The fringe will be a pripority queue in general to just store the node to be visited. For BFS and DFS respectively, it can be reduced to queue and stack respectively. For graph search, the close set will be used to store the nodes that all child nodes have been visited in order to prune unnecessary duplicated search.

Consider a search tree that each node has b child nodes and m tiers.

Time Complexity: DFS takes O(b^m) to find one solution while BFS takes O(b^s) to find one, where s is the depth of the shallowest solution.

Space Complexity: Here the space complexity refers to the largest size that fringe will ever consume. DFS only takes O(bm) since it only need to store the slibing nodes on the path to root, while BFS takes roughly the last tier, i.e. O(b^s)

Here are the illustration for DFS vs BFS:

We can easily see that in most case, it is faster to use BFS than DFS to find one solution, but DFS takes less memory than BFS. ID-DFS is, therefore, nothing but a combination of BFS and DFS. So to search up to depth d, the memory consumption is the same as DFS, namely O(bd).