Iterative deepening depth-first search
From Wikipedia, the free encyclopedia
| Graph search algorithms |
|---|
| Search |
Iterative deepening depth-first search or IDDFS is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state. On each iteration, the IDDFS visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited, assuming no pruning, is effectively breadth-first.
Iterative deepening depth-first search combines depth-first search's space-efficiency and breadth-first search's completeness (when the branching factor is finite). Search is optimal when the path cost is a non-decreasing function(monotone) of the depth of the node.
The space complexity of IDDFS is O(bd), where b 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.
The main advantage of this algorithm in game tree searching is that the earlier searches tend to improve the commonly used heuristics, such as the killer heuristic and alpha-beta pruning, so that a more accurate estimate of the score of various nodes at the final depth search can occur, and the search completes more quickly since it is done in a better order (it can be shown that alpha-beta pruning works much better if the moves are generated with the moves likely to be the best moves evaluated first). A second advantage is the responsiveness of the algorithm. Because early iterations use small values for d, they execute extremely quickly. This allows the algorithm to supply early indications of the result almost immediately, followed by refinements as d increases. When employed in an interactive setting such as in a chess playing program this facility is very useful to the end user, allowing them a "Play Now" functionality. If the user asks the computer to "play now", it can base its move on whatever depth of search it has completed so far. This is not possible with a traditional Depth-first search.
In fact the time complexity of IDDFS in well balanced trees works out to be the same as Depth-first search — O(bd).
Similar to iterative deepening is a search strategy called iterative lengthening search that works with increasing path-cost limits instead of depth-limits. The algorithm expands nodes in the order of increasing path cost; therefore the first goal it encounters is the one with the cheapest path cost. It turns out however, that iterative lengthening incurs substantial overhead that make it less useful than iterative deepening as a search strategy.
In an iterative deepening search, the nodes on the bottom level are expanded once, those on the next to bottom level are expanded twice, and so on, up to the root of the search tree, which is expanded d + 1 times. So the total number of expansions in an iterative deepening search is
(d + 1)1 + (d)b + (d- 1)b2 + ••• + 3bd − 2 + 2bd − 1 + bd
Again, for b = 10 and d = 5 the number is
6 + 50 + 400 + 3,000 + 20,000+100,000= 123,456
All together, an iterative deepening search from depth 1 all the way down to depth d expands only about 11 % more nodes than a single breadth-first or depth-limited search to depth d, when b = 10. The higher the branching factor, the lower the overhead of repeatedly expanded states, but even when the branching factor is 2, iterative deepening search only takes about twice as long as a complete breadth-first search. This means that the time complexity of iterative deepening is still O(bd), and the space complexity is O(bd). In general, iterative deepening is the preferred search method when there is a large search space and the depth of the solution is not known.[1]
[edit] Notes
- ^ Russell, Stuart J. & Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, NJ: Prentice Hall, ISBN 0-13-790395-2, <http://aima.cs.berkeley.edu/>
