How is iterative deepening more efficient than just scanning the nodes at a specified depth level.

Isn't it redundant to rescan n-1 levels of nodes f开发者_运维问答or each iteration?

I quote from Artificial Intelligence: A Modern Approach:

Iterative deepening search may seem wasteful because states are generated multiple times. It turns out this is not too costly. The reason is that in a search tree with the same (or nearly the same) branching factor at each level, most of the nodes are in the bottom level, so it does not matter much that the upper levels are generated multiple times. In an iterative deepening search, the nodes on the bottom level (depth d) are generated once, those on the next-to-bottom level are generated twice, and so on, up to the children of the root, which are generated d times. So the total number of nodes generated in the worst case is

N(IDS) = (d)*b+(d-1)*b^2+...+(1)*b^d

which gives a time complexity of O(b^d) - asymptotically the same as breadth-first search.