;;; ida.lisp ;;;; Iterative Deepening A* (IDA*) Search (defun tree-ida*-search (problem) "Iterative Deepening Tree-A* Search [p 107]." ;; The main loop does a series of f-cost-bounded depth-first ;; searches until a solution is found. After each search, the f-cost ;; bound is increased to the smallest f-cost value found that ;; exceeds the previous bound. Note that the variables here are ;; local, not static as on [p 107]. (setf (problem-iterative? problem) t) (let* ((root (create-start-node problem)) (f-limit (node-f-cost root)) (solution nil)) (loop (multiple-value-setq (solution f-limit) (DFS-contour root problem f-limit)) (dprint "DFS-contour returned" solution "at" f-limit) (if (not (null solution)) (RETURN solution)) (if (= f-limit infinity) (RETURN nil))))) (defun DFS-contour (node problem f-limit) "Return a solution and a new f-cost limit." (let ((next-f infinity)) (cond ((> (node-f-cost node) f-limit) (values nil (node-f-cost node))) ((goal-test problem (node-state node)) (values node f-limit)) (t (for each s in (expand node problem) do (multiple-value-bind (solution new-f) (DFS-contour s problem f-limit) (if (not (null solution)) (RETURN-FROM DFS-contour (values solution f-limit))) (setq next-f (min next-f new-f)))) (values nil next-f)))))