home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
rtsi.com
/
2014.01.www.rtsi.com.tar
/
www.rtsi.com
/
OS9
/
OSK
/
EFFO
/
forum3.lzh
/
LISP
/
search.lsp
< prev
Wrap
Lisp/Scheme
|
1987-11-19
|
5KB
|
105 lines
; 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)))))