About Depth Limited Searching
Traditional depth first search could be deemed useless in infinite state spaces as they will continue to traverse down the leftmost branch infinitely. This essentially means that the path to the goal node might never be found, in order to combat this we can add a limit to the depth that our search recurses down the tree, this essentially transforms our depth first algorithm into a depth-limited algorithm.
This algorithm can fail in two different ways. First is that no goal node is found in the graph and the other is the cutoff type of failure in which no goal node is found within the set depth.
This algorithm basically follows the same methods as the depth first search.
- Node 1 is added to the stack
- If Node 1 is not the goal node then add Node 2 to the stack
- If Node 2 is not the goal node then add Node 4 to the stack
- If Node 4 is not the goal node and depth limit has been reached then revert to nearest Node with unexplored children and add these to stack
- continue until all nodes within depth limit have been searched or goal node has been found.
Depth First Search:
For more information about the search based algorithm that this is based off, you can check out this tutorial here: Depth First Search in Java
Below you’ll find an implementation of a Depth-Limited search class which is built as an extension of the AbstractSearch java class.
AbstractSearch Java Class:
Depth Limited Search Class