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(bd)
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
  1. Run algorithm, with level = 1.
    1. We start from the root node A.
    2. We check to see if A is a goal node. It's not, so we continue.
    3. There are no more nodes, so we increase the level and re-run the algorithm.
  2. Run the algorithm, with level = 2.
    1. We start from the root node A.
    2. 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.
    3. We check to see if B is a goal node. It's not, so we continue.
    4. We check to see if C is a goal node. It's not, so we continue.
    5. There are no more nodes, so we increase the level and re-run the algorithm.
  3. Run the algorithm, with level = 3.
    1. We start from the root node A.
    2. 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.
    3. 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.
    4. We remove node D from the frontier, we check if it's a goal node. It's not, so we continue.
    5. We remove node E from the frontier, we check if it's a goal node. It's not, so we continue.
    6. 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.
    7. 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


Return to Articles