Catalogue of Artificial Intelligence Techniques
Keywords: admissibility, games
Author(s): Frank van Harmelen
An uninformed graph search algorithm which is a good compromise between the efficiency of Depth-first Search and the admissibility of Breadth-first Search. Iterative deepening performs a complete search of the Search Space (often using a depth-first search strategy) up to a maximum depth . If no solutions can be found up to depth , the maximum search depth is increased to , and the search space is traversed again (starting from the top node). This strategy ensures that iterative deepening, like breadth-first search, always terminates in an optimal path from the start node to a goal node whenever such a path exists (this is called admissibility); but it also allows implementation as an efficient depth-first search. Iterative deepening is optimal in both time and space complexity among all uninformed admissible search strategies. At first sight it might look as if iterative deepening is inefficient, since after increasing the cut-off depth from to , it redoes all the work up to level in order to investigate nodes at level
. However, since typical search spaces grow exponentially with
(because of a constant branching factor), the cost of searching up to depth is entirely dominated by the search at the deepest level : If is the average branching rate of the search space, there are nodes at depth , which is the same as the total number of nodes up to depth . In fact, it can be shown that among all uninformed admissible search strategies, iterative deepening has the lowest asymptotic complexity in both time ( ) and space ( ). Breadth-first search on the other hand is only asymptotically optimal in time, and is very bad (exponential) in space. The actual time complexity of breadth-first search (as opposed to the asymptotic complexity) is of course lower than that for iterative deepening (namely by the small constant factor ), but this is easily offset by the difference in space-complexity in favour of iterative-deepening. Thus, iterative-deepening is asymptotically optimal in both time and space, whereas breadth-first is asymptotically optimal only in time and really bad in space, while the actual complexities of iterative-deepening and breadth-first are very close. Iterative deepening can also be applied to informed search strategies, such as A*. This modified version of A* is again optimal in both time and space among all informed admissible search strategies.
- Korf, R.E., Search: A Survey of Recent Results, Exploring Artificial Intelligence (Survey talks from the National Conferences on Artificial Intelligence)
, ed.), Morgan Kaufmann, San Mateo, California, 1988, pp.197--237 (Chapter 6).