Iterative deepening depth-first search
|
|
Iterative deepening depth-first search is a states-space search strategy, that visits each node in the search tree in the same order as depth-first search but does so by gradually increasing the maximum depth limit of the search iteratively. At each iteration, the maximum depth is increased and the search is re-run. This is repeated until the depth limit reaches <math>d<math>, the depth of the shallowest goal state. Iterative Deepening can be effectively considered as the repeated application of depth-limited search, increasing the bound with each iteration.
Iterative deepening depth-first search combines the best features of depth-first search ie. space-efficiency and breadth-first search, ie. completeness when the branching factor is finite and optimality when the path cost is a non-decreasing function of the depth of the node.
The space complexity of ITDFS is O(bd), where <math>b<math> is the branching factor. 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. In fact the time complexity of ITDFS works out to be the same as Depth-first or Breadth-first search — <math>O(b^{d+1})<math>.
Similar to Iterative deepening is a search strategy called Iterative lengthening search that works with increasing path-cost limits instead of depth-limits. It turns out however, that iterative lengthening incurs substantial overhead that make it less useful than iterative deepening as a search strategy.de:Iterative Tiefensuche