EK201 HAND-OUT
MARCH 30, 1987

ONE LINE NOTES:
 ~gjc/queue.l answer to the queue problem set.
 ~gjc/search.l and search-test.l * the simple generic node visitation
  procedures you will build your problem set from.

In the last two lectures and in your homework due this WED we
have been studing the use of queue's in keeping track of
intermediate solutions to graph visitation and traversal problems.

* by Path we be either back-tracking or non-back-tracking.
* Modify or build on search.l to provide a procedure to compute
  all paths from point-a to point-b.
* Modify this to provide all paths of a given length from point-a to point-b.
* Modify this to provide all PATHS of a given length.

Recall that the combination of a LIFO stack and back-tracking paths
we get indefinite recursion.

Lets look at how these problems we be solved recursively,
as in chapter 11 of the winston/horn book. First, our favorite graph:

          / E--------F
        /    \       |
     /--B-----C------G
   A           \
    \----------- D

represented as

(defprop a (b d) connections)
(defprop b (a c e) connections)
(defprop c (b d e g) connections)
(defprop d (a c) connections)
(defprop e (b c f) connections)
(defprop f (e g) connections)
(defprop g (c f) connections)

Then, the to compute all paths connecting two points
(as in the homework problem):


(defun print-all-paths (from to)
  (ppath (list from) to))

(defun ppath (sofar goal)
  (cond ((eq (car sofar) goal)
	 (print (reverse sofar))
	 ())
	('else
	 (dolist (next (possible-routes sofar))
	   (ppath next goal)))))

(defun possible-routes (sofar)
  (let ((ok nil))
    (dolist (c (get (car sofar) 'connections))
      (or (memq c sofar)
	  (push (cons c sofar) ok)))
    (reverse ok)))

* Class discussion topic: Which kind of queue would this recursive
implementation emulate, LIFO or FIFO?

* game trees. How can these be efficiently computed.
  How to use the generalize tree concept of ~gjc/visit.l
  to implement a tic-tac-toe game tree.