;Here we describe the Depth-bounded depth-first search once again in order to
;develop the Iterative Deepening Depth-first Search.
;First, the main calling function is detailed that accepts as input the
;PROBLEM SPECIFICATION as well as the DEPTH to which a search will be
;conducted...
;Note how the initial state is turned into a node and passed down to the
;recursive version of the depth first search...
(defun dfs (s0 sg sons depth-bound)
(depth-bounded-dfs
(list s0 nil nil) ;remember, this is a node
sg ;this is the goal state
sons ;this is the successor generator
depth-bound) ;and the depth bound to which we search
) ;ends defun
;That's it. It simply calls another recursive function. Here we go...
;We split this function out separately so that we can specify search
;over "NODES" (not states) recursively...
(defun depth-bounded-dfs (node goal succesors depth)
(let (DBDFS (daughters nil) ) ;Hmmmm...where did Open, Closed and N go?
(if (**equal** (state node) goal) (return-from DBDFS (trace-solution node)))
(if (= depth 1) (return-from DBDFS nil)) ;bottomed out in the search space
;without finding a goal down this path
(setf daughters (successors node)) ;presumably we have a LIST of derived
;children NODES
;(What happened to DIFF?..do we care?)
(loop ;so we iterate down them looking for
;a solution path...this could easily
;be changed to a do form....
(if (null daughters) (return-from DBDFS nil)) ;failed to find a solution
(if (depth-bounded-dfs ;recursive call with
(pop daughters) ;the first of daughters& daughters updated
goal ;same old goal state
successors ;same old set of operators
(- depth 1)) ;but a shallower depth!
(return-from DBDFS t) ;here we did find a solution so we leave happy
) ;end if
) ;ends loop
) ;ends let
) ;ends defun {otherwise known as "]" :) }
;That's it folks!
;Now, for the iterative deepening DFS, here we go:
(defun Iterative-deepening-dfs (s0 sg sons depth INCREMENT)
(if
(dfs s0 sg sons depth) ;call dfs directly to depth
(return t) ;solution found if dfs is true, so return t
(Iterative-deepening-dfs ;else, try again but more deeply!
s0 ;the same initial state
sg ;the same old goal state
sons ;the same old set of operators
(+ depth INCREMENT) ;but now a deeper search!
INCREMENT) ;and increment again later if you don't succeed
) ;ends if
) ;ends defun