;;; ======================================================================
;;; Code that implements search examples following presentation in Norvig
;;; section 6.4. 2/95 Paul McNamee
(in-package :user)
;;; ======================================================================
;;; A general tree searching tool.
(defun tree-search (states goal-p successor-fn combiner-fn)
"Find a state that statisfies goal-p. General tool that can implement
different types of searches by changing the combination rules."
(format t "~&;; Search: ~S" states)
(cond ((null states) (format t "Failed to find a solution.~%"))
((funcall goal-p (first states)) (first states))
(t (tree-search (funcall combiner-fn
(funcall successor-fn (first states))
(rest states))
goal-p successor-fn combiner-fn))
))
;;; ======================================================================
;;; Depth-First-Search based on tree-search
(defun depth-first-search (start goal-p successor-fn)
"DFS using general tree searching utility"
(tree-search (list start) goal-p successor-fn #'append)
)
;;; ======================================================================
;;; Breadth-First-Search based on tree-search. The difference here is we
;;; want to examine the rest of the states first, then the children of the
;;; first state. This is the opposite of append.
(defun prepend (a b)
"Opposite of (append a b)"
(append b a))
(defun breadth-first-search (start goal-p successor-fn)
"BFS using general tree searching utility"
(tree-search (list start) goal-p successor-fn #'prepend)
)
;;; ======================================================================
(defun Print-Book (book stream k)
(declare (ignore k))
"I can't remember what k is for, but print function should have 3 args. cf Steele pg 480"
(format stream "" (node-title book) (node-author book))
)
(defstruct (Node (:print-function print-book))
(author "" :type 'string) (title "" :type 'string) (left-child nil) (right-child nil))
(defparameter *Library* (make-node :author "Norvig" :title "PAIP")
"A tree containing some of Paul's favorite books sorted by author name")
(defun Add-Book (author title &key (node *Library*))
(cond ((string< author (node-author node))
(if (null (node-left-child node))
(setf (node-left-child node)
(make-node :author author :title title))
(Add-Book author title :node (node-left-child node))) )
(t (if (null (node-right-child node))
(setf (node-right-child node) (make-node :author author :title title))
(Add-Book author title :node (node-right-child node))) )
))
(defun Create-Tree ()
(Add-Book "Weiss" "The Swiss Family Robinson")
(Add-Book "Steele" "CLTL2")
(Add-Book "Conan Doyle" "Adventures of Sherlock Holmes")
(Add-Book "Kernighan & Ritchie" "The C Programming Language 2nd edition")
(Add-Book "Clocksin & Mellish" "Programming in Prolog")
(Add-Book "Verne" "Journey to the Center of the Earth")
(Add-Book "Tolkien" "The Hobbit")
)
(defun Print-Library (&optional (node *library*))
"In Order Traversal"
(cond ((null node) (values))
(t (Print-Library (node-left-child node))
(format t "~S~%" (node-author node))
(Print-Library (node-right-child node)) )
))
(defun Author-Equal-Fn (x)
"Returns a function of one argument that checks to see if a book author field contains x.
Note that search is used to check for subsequences"
#'(lambda (y) (search x (node-author y) :test #'string-equal))
)
(defun Title-Equal-Fn (x)
"Returns a function of one argument that checks to see if a book author field contains x.
Note that search is used to check for subsequences"
#'(lambda (y) (search x (node-title y) :test #'string-equal))
)
(defun Children-of-Book (node)
(remove-if #'null (list (node-left-child node) (node-right-child node)))
)
;;; ======================================================================
;;; Okay this was a nice example of searching trees. The tree structure here
;;; gave us Logrithmic time instead of linear which we would have in a list.
;;;
;;; Another application of search is State Space Search. In this case we are
;;; concerned with searching a universe of possible solutions and finding
;;; a solution. (Sometimes we want the _best_ solution). Common examples of
;;; State Space Search are:
;;; - path planning
;;; - game playing (eg. chess)
;;; - TSP / network problems. (goals could be shortest distance, max throughput, ...)
;;; ======================================================================