State Space Search : Depth bounded DFS

 Depth bounded DFS algorithm is different from DFS , in that it takes a parameter for depth bound. Given  any node, it calls moveGen only if it is within the given depth bound. The node representation is changed to include depth of node as the third parameter, apart from the parent link, which is the second parameter. The function makePairs is modified appropriate to compute the depth of a node, by adding one to the depth of its parent. The Reader would have observed that implementing DBDFS would have been simpler with the nobel representations that stored the complete path.  One would just have to look at the length of the node to determine whether one is within the allowable bound. And in addition, the task of reconstructing the path is also simplified. Obviously, various design choices will have to be made while implementing solutions for specific problems. Performance wise the DBDFS is like DFS or a finite tree. However, given that the Depth bound is artificially imposed, the algorithm is not complete in the general case.

DepthBoundedDFS (start, depthBounded)

   open - ( (start, NIL, 0) )

   closed - ( )

   while not Null (open)

      do nodePair - Head (open)

       node - Head(nodePair)

       if GoalTest (node) = TRUE

             then return ReconstructPath (nodePair, closed)

             else closed - Cons (nodePair, closed)

                 if Head(Rest (Rest (nodePair) ) ) < depthBound

                 then children - MoveGen (node)

                     noL.oops - RemoveSeen(children, open, closed)

                     new - MakePairs(noLoops, node, Head(Rest (Rest(nodePair) ) ) )

                     open - Append(new, Tail(open) )

  return "No solution found"

MakePairs (list, parent, depth)

   if Null(list)

      then return ()

      else return (Cons (MakeList( Head (list), parent, depth+1 ) ),

                          MakePairs (Tail(list), parent, depth) )

Depth Bounded DFS generates new nodes only within a defined boundary