For this example, assume that the level value is 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 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.