Iterative Deepening Search
No longer a simple instance of general search
- d = min-d
- Loop Until (solution found)
- apply DFDB(d)
- d := d + increment
Why?
- Guarantees to find a solution if one exists (cf DFDB)
- Finds shallow solutions first (cf DF)
- Always has small frontier (cf Breadth First)
- Surprising asymptotic guarantees
- search time typically no more than d/(d-1) as bad as DF
-
-