function DEPTH-LIMITED-SEARCH(problem, l) returns a solution, or failure, or cutoff
frontier ← a FIFO queue initially containing one path, for the problem's initial state
solution ← failure
while frontier is not empty do
parent ← pop(frontier)
if depth(parent) > l then
solution ← cutoff
else
for child in successors(parent) do
if child is a goal then
return child
add child to frontier
return solution
Figure 3.14 An implementation of depth-limited tree search. The algorithm has two dif- ferent ways to signal failure to find a solution: it returns failure when it has exhausted all paths and proved there is no solution at any depth, and returns cutoff to mean there might be a solution at a deeper depth than l. Note that this algorithm does not keep track of reached states, and thus might visit the same state multiple times on different paths.
function DEPTH-LIMITED-SEARCH(problem,limit) returns a solution, or failure/cutoff
return RECURSIVE-DLS(MAKE-NODE(problem.INITIAL-STATE),problem,limit)
function RECURSIVE-DLS(node,problem,limit) returns a solution, or failure/cutoff
if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
else if limit = 0 then return cutoff
else
cutoff_occurred? ← false
for each action in problem.ACTIONS(node.STATE) do
child ← CHILD-NODE(problem,node,action)
result ← RECURSIVE-DLS(child,problem,limit-1)
if result = cutoff then cutoff_occurred? ← true
else if result ≠ failure then return result
if cutoff_occurred? then return cutoff else return failure
Figure ?? A recursive implementation of depth-limited tree search.