Introduction to Artificial Intelligence
Worksheet #3
Depth and Breadth First Searching

Using the code below answer the questions.           Draw the graph for these putprops


(Defun Search (Start Finish)                           (Putprop 'S '(A B) 'Adjacent)
   (Searcher (list (list start)) finish)               (Putprop 'A '(S B F) 'Adjacent)
)                                                      (Putprop 'B '(S A C) 'Adjacent)
                                                       (Putprop 'C '(B F) 'Adjacent)
(Defun Searcher (SorQ Final)                           (Putprop 'F '(A C) 'Adjacent)
   (Cond ((Null SorQ) Nil)
         ((Equal Final (first (first SorQ))) (reverse (car SorQ)))
         (T (Searcher (append (Expand (first SorQ)) (rest SorQ)) Final))
   )
)
(Defun Expand (Path)
   (mapcar '(lambda (Node) (cons Node Path))  (get (car Path) 'Adjacent)) 
)

  1. Run the code given above for (Search 's 'f). Trace the calls on screen.
    Describe the results below.



  2. Change the original code so that the list of paths to be checked is constructed
    more like a queue. Repeat #1 on this new version.



  3. In the original program change expand to remove the circular paths. Repeat #1.



  4. Enlarge the graph by adding several more nodes, not necessarily doubly connected.
    Draw this graph above in the space next to the putprops.



  5. Explain the differences in the paths you obtained using the 3 different algorithms.



  6. Print out code for all 3 (with runs.) Circle or highlight changes you made to the code.