# 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

• Abbreviated as DLS.
• DLS is DFS, but with a defined depth limit that we call level. Nodes below the level are completely ignored by the DLS algorithm.
• This solves the infinite loop problem with the tree search variant of DFS.
• There is no correct way to choose a level value.
• If the level is too low, then the goal may never be found.
For example, say we set our level to 2 and then re-run the DLS algorithm on the tree above. We would never find a solution, because both goal nodes are past the level limit.
• If the level is too high, then an optimal solution may not be found.
For example, say we set our level to 4 and then re-run the DLS algorithm on the tree above. We would still find a solution, the path to node 'K', but it wouldn't be the optimal solution, the path to node F.