Iterative Deepening Search
Published
Completeness 
 
Complete if the branching factor is finite. 
Optimality 
 
Optimal if the costs of all actions are equal. 
Time Complexity 
 
O(b^{d}) 
Space Complexity 
 
O(b × d) 
Visual Example

level 
Current Node 
Frontier 
1 
A 

2 
A 
B, C 
2 
B 
C 
2 
C 

3 
A 
B, C 
3 
B 
D, E, C 
3 
D 
E, C 
3 
E 
C 
3 
C 
F, G 
3 
F 
G 
Goal Node Found 

 Run algorithm, with level = 1.
 We start from the root node A.
 We check to see if A is a goal node. It's not, so we continue.
 There are no more nodes, so we increase the level and rerun the algorithm.
 Run the algorithm, with level = 2.
 We start from the root node A.
 We check to see if A is a goal node. It's not, so we add it's children, nodes B and C, to the frontier.
 We check to see if B is a goal node. It's not, so we continue.
 We check to see if C is a goal node. It's not, so we continue.
 There are no more nodes, so we increase the level and rerun the algorithm.
 Run the algorithm, with level = 3.
 We start from the root node A.
 We check to see if A is a goal node. It's not, so we add it's children, nodes B and C, to the frontier.
 We remove node B from the frontier, we check if it's a goal node. It's not, so we add it's children, nodes D and E, to the frontier.
 We remove node D from the frontier, we check if it's a goal node. It's not, so we continue.
 We remove node E from the frontier, we check if it's a goal node. It's not, so we continue.
 We remove node C from the frontier, we check if it's a goal node. It's not, so we add it's children, nodes F and G, to the frontier.
 We remove node F from the frontier, we check if it's a goal node. It is, so we're done.
Nodes H, I, J, and K are never visited because our level value never reaches 4.
Algorithm Notes
 Abbreviated as IDS.

IDS is DLS, but it differs from DLS in that IDS increases the level and reruns the
algorithm every time it fails to find a goal node.
 This is generally the preferred uninformed search method if the search space is large and the depth (level) of the goal is unknown.
 The main disadvantage of IDS is that some nodes are visited many times. However, this is not usually an issue.
Return to Articles