;; -*- Mode: Lisp -*-

;;;; Simple Search Algorithms

;;; Here we define the GENERAL-SEARCH function, and then a set of
;;; search functions that follow specific search strategies.  None of
;;; these algorithms worries about repeated states in the search.

(defun general-search (problem queuing-fn)
  "Expand nodes according to the specification of PROBLEM until we find
  a solution or run out of nodes to expand.  The QUEUING-FN decides which
  nodes to look at first. [p 73]"
  (let ((nodes (make-initial-queue problem queuing-fn))
	node)
    (loop (if (empty-queue? nodes) (RETURN nil))
	  (setq node (remove-front nodes))
	  (if (goal-test problem (node-state node)) (RETURN node))
	  (funcall queuing-fn nodes (expand node problem)))))

(defun breadth-first-search (problem)
  "Search the shallowest nodes in the search tree first. [p 74]"
  (general-search problem #'enqueue-at-end))

(defun depth-first-search (problem)
  "Search the deepest nodes in the search tree first. [p 78]"
  (general-search problem #'enqueue-at-front))

(defun iterative-deepening-search (problem)
  "Do a series of depth-limited searches, increasing depth each time. [p 79]"
  (for depth = 0 to infinity do
       (let ((solution (depth-limited-search problem depth)))
	 (unless (eq solution :cut-off) (RETURN solution)))))

(defun depth-limited-search (problem &optional (limit infinity)
                                     (node (create-start-node problem)))
  "Search depth-first, but only up to LIMIT branches deep in the tree."
  (cond ((goal-test problem node) node)
        ((>= (node-depth node) limit) :cut-off)
        (t (for each n in (expand node problem) do
		(let ((solution (depth-limited-search problem limit n)))
		  (when solution (RETURN solution)))))))

;;;; Search Algorithms That Use Heuristic Information

(defun best-first-search (problem eval-fn)
  "Search the nodes with the best evaluation first. [p 93]"
  (general-search problem #'(lambda (old-q nodes) 
			      (enqueue-by-priority old-q nodes eval-fn))))

(defun greedy-search (problem)
  "Best-first search using H (heuristic distance to goal). [p 93]"
  (best-first-search problem #'node-h-cost))

(defun tree-a*-search (problem)
  "Best-first search using estimated total cost, or (F = G + H). [p 97]"
  (best-first-search problem #'node-f-cost))

(defun uniform-cost-search (problem)
  "Best-first search using the node's depth as its cost.  Discussion on [p 75]"
  (best-first-search problem #'node-depth))

;;;; Utility Function

(defun make-initial-queue (problem queuing-fn)
  (let ((q (make-empty-queue)))
    (funcall queuing-fn q (list (create-start-node problem)))
    q))