;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