Depth-Limited Search

Published
Completeness - Complete if level ≥ the depth of the goal node.
Optimality - Optimal if level is the depth of the goal node.
Time Complexity - O(blevel)
Space Complexity - O(b × level)

Visual Example

Current Node Frontier
A B, C
B D, E, C
D E, C
E C
C F, G
F G
Goal Node Found
For this example, assume that the level value is 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 is 3. This means that we only explore the first three levels of nodes.

Algorithm Notes


Return to Articles