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