Iterative Deepening
Algorithm
Time Space complexity complexity
Complete Yes* Yes**
Optimal No Yes***
Depth‐first search
Breadth‐first search
*If m is finite. **if d is finite. ***if all actions have the same cost.
Idea: get the space advantage of DFS with time/optimality advantages of BFS
Steps:
Run DFS with depth 1.
if no solution, run DFS with depth 2. If no solution, run DFS with depth 3. …
Iterative Deepening
Algorithm
Time Space complexity complexity
Complete Yes* Yes** Yes**
Optimal No Yes*** Yes***
Depth‐first search
Breadth‐first search
Iterative Deepening
*If m is finite. **if d is finite. ***if all actions have the same cost. b is branching factor;
d is depth of the shallowest goal;
m is depth of entire tree.
Some redundancy
Since most work happens in the lowest
layers searched, so not very bad
Closed list
A
CG
Closed list is a list of nodes that have been expanded to avoid repeatedly expanding the same node multiple times.
S
S
B
A BCC
CGG G
B
Example: BFS with closed list
S
B
A BCC
A
CG
S
B
S A B C
CGG G