Lesson 9
Write a lisp program solving the search problem beneath using depth first search. (A simplified version of the farmer, goat etc. problem, use "OR", but no need for "SAFE")
S ---> A ---> B
| |
| |
v v
C ---> D ---> G
Solution:
S ---> A ---> B >(depth 's nil)
| | 1> (DEPTH S NIL)
| | 2> (RIGHT S)
v v <2 (RIGHT A)
C ---> D ---> G 2> (DEPTH A (S))
3> (RIGHT A)
(defun right (state) <3 (RIGHT B)
(cond ((equal state 's) 'a) 3> (DEPTH B (A S))
((equal state 'a) 'b) 4> (RIGHT B)
((equal state 'c) 'd) <4 (RIGHT NIL)
((equal state 'd) 'g) 4> (DEPTH NIL (B A S))
(t nil))) <4 (DEPTH NIL)
4> (DOWN B)
(defun down (state) <4 (DOWN NIL)
(cond ((equal state 's) 'c) 4> (DEPTH NIL (B A S))
((equal state 'a) 'd) <4 (DEPTH NIL)
(t nil))) <3 (DEPTH NIL)
3> (DOWN A)
(defun depth (s p) <3 (DOWN D)
(cond ((null s) nil) 3> (DEPTH D (A S))
((equal s 'g)
(reverse (cons s p))) 4> (RIGHT D)
((member s p) nil) <4 (RIGHT G)
(t (or (depth (right s)
(cons s p)) 4> (DEPTH G (D A S))
(depth (down s)
(cons s p)))))) <4 (DEPTH (S A D G))
<3 (DEPTH (S A D G))
<2 (DEPTH (S A D G))
<1 (DEPTH (S A D G))
(S A D G)
Search problems from page 9 in the handout, sorry they are in Swedish!
Last modified: Mon Apr 26 11:15:02 MEST 2004