;;; 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)))))