home *** CD-ROM | disk | FTP | other *** search
- ; File SEARCH.LSP, by Christopher F. Chabris, October 1986
- ; This file contains XLisp 1.7 functions to implement basic breadth-first
- ; and depth-first search algorithms, as well as a simple state-space for
- ; the route-finding problem. (For ST XLisp-AI Conference #3, 10/6/86.)
-
-
- ; First, we define the state-space we will be searching through with a few
- ; simple PUTPROP calls that specify for each state, or city, the other
- ; states that can be reached from it with one operator. For pedagogical
- ; purposes, we will not specify the operators themselves, just their effects.
- ; Also note that there is one PUTPROP for each state in the state-space, and
- ; that you can make such code quite readable despite all the parentheses!
-
- (putprop 'hanover '(cambridge ithaca) 'successors)
- (putprop 'cambridge '(hanover providence) 'successors)
- (putprop 'providence '(cambridge newhaven) 'successors)
- (putprop 'newhaven '(providence newyork) 'successors)
- (putprop 'newyork '(newhaven ithaca princeton) 'successors)
- (putprop 'ithaca '(hanover newyork philadelphia) 'successors)
- (putprop 'princeton '(newyork philadelphia) 'successors)
- (putprop 'philadelphia '(princeton ithaca) 'successors)
-
-
- ; Now we define the top level breadth-first and depth-first functions. Note
- ; that the only difference between the two is how the OPEN list, which
- ; contains the yet unexplored states at any given time, is formed (this is
- ; done in the fourth line of the BFS and DFS function definitions). The
- ; BFS algorithm adds new child states to the end of OPEN, while DFS adds
- ; them to the beginning. I am always impressed by the way a small nuance
- ; can control the behavior of a relatively complex algorithm. Later, we
- ; will see how we can add "intelligence" to the basic algorithms given here
- ; with just a few modifications. The same framework covers most of the
- ; search strategies popular in AI programming.
-
- (defun breadth-first-search (start goal)
- (setq *goal-node* goal)
- (bfs (list (list start nil)) nil))
-
- (defun bfs (open closed)
- (cond ((null open) nil)
- ((goal (car open)) (findpath (cons (car open) closed) (caar open)))
- (t (bfs (append (cdr open) (prune (children (car open)) open closed))
- (cons (car open) closed)))))
-
- (defun depth-first-search (start goal)
- (setq *goal-node* goal)
- (dfs (list (list start nil)) nil))
-
- (defun dfs (open closed)
- (cond ((null open) nil)
- ((goal (car open)) (findpath (cons (car open) closed) (caar open)))
- (t (dfs (append (prune (children (car open)) open closed) (cdr open))
- (cons (car open) closed)))))
-
-
- ; Now we define the various supporting functions that were called by the
- ; above functions: GOAL, which returns T if a given node is a goal node,
- ; or NIL otherwise; CHILDREN, which returns a list of nodes that are the
- ; successors of a given node; FINDPATH, which takes a node and the CLOSED
- ; list and returns a path back to the start node; and PRUNE, which takes
- ; a list of nodes (usually the generated successors) and the OPEN and
- ; CLOSED lists and removes from the first nodes that are contained in the
- ; other two (this has the effect of avoiding the cycling problem in search).
-
- (defun goal (node)
- (equal *goal-node* (car node)))
-
- (defun children (node)
- (let ((successors (get (car node) 'successors)))
- (mapcar 'list successors (make-list (length successors) (car node)))))
-
-
- (defun findpath (nodelist state)
- (cond ((null state) nil)
- ((equal state (caar nodelist))
- (append (findpath (cdr nodelist) (cadar nodelist)) (list state)))
- (t (findpath (cdr nodelist) state))))
-
-
- (defun prune (nodelist open closed)
- (cond ((null nodelist) nil)
- ((or (member (caar nodelist) (mapcar 'car open))
- (member (caar nodelist) (mapcar 'car closed)))
- (prune (cdr nodelist) open closed))
- (t (cons (car nodelist) (prune (cdr nodelist) open closed)))))
-
-
- ; A note on representation: the OPEN and CLOSED lists are represented as
- ; "association lists", which are just Lisp lists where each member is a
- ; two-element list itself. (Although XLisp has special functions to
- ; manipulate A-lists, we do not use them here.) Our functions treat the
- ; first element of each pair as a state (city) and the second element as
- ; that state's parent (the state from which it was generated). This way,
- ; we can use the pairs on the CLOSED list of explored states to trace the
- ; path back to the start state.
-
-
- ; This final function, MAKE-LIST, takes a number n and any expression and
- ; returns a list of length n, with each element being that expression. A
- ; similar function is built into Common Lisp, but not XLisp 1.7.
-
- (defun make-list (size expr)
- (cond ((zerop size) nil)
- (t (cons expr (make-list (1- size) expr)))))
-