Q about Problem 19-2 in "Lisp" by Winston and Horn
Paul Reiners
search, all of the partial paths in the queue at a given point in the
search are related to one another in a simple way: each is the
extension by one node of the partial path after it in the queue. The
queue might, for example, look like this:
((D C B A) (C B A) (B A) (A))
"
However, I don't see how that's the case. For example, I get output
like the following:
(depth-first 's 'f)
queue: ((S))
(S)
queue: ((A S) (D S))
(S A)
queue: ((B A S) (D A S) (D S))
(S A B)
queue: ((C B A S) (E B A S) (D A S) (D S))
(S A B C)
queue: ((E B A S) (D A S) (D S))
(S A B E)
queue: ((D E B A S) (F E B A S) (D A S) (D S))
(S A B E D)
queue: ((F E B A S) (D A S) (D S))
(S A B E F)
where I put a print statement at the beginning of the routine:
(defun depth-first (start finish &optional
(queue (list (list start))))
(format t "~%queue: ~a" queue)
(cond ((endp queue) nil)
((eq finish (first (first queue)))
(reverse (first queue)))
(t (depth-first
start
finish
(append (extend (first queue))
(rest queue))))))
In this case, no partial path in the queue is the extension by one
node of the partial path after it in the queue.
Is this a misprint in the exercise or is there some input that does
actually give the queue he gives?
Pascal J. Bourguignon
You're right.
What was meant, concerns either the paths printed by EXTEND, or is
that each path in the result of (extend (first queue)) is the
extension by one node of the partial path (first queue).
Conceptually, the searches walk a tree (the search tree). If you
label each node of that search tree with the the first element of the
queue, you will see that each child node is labelled with the extended
paths, which have one more node prepened to the path of the parent.
There's something "magic" happening in extend in that if all the
neighbors are already in the path, then it returns an empty list,
which appended to the rest of the queue is equivalent to having
removed the first path in the queue (which is a dead-end). This
operations makes up come back to an upper node in the search tree.
(defun clear-graph (nodes)
(loop for node in nodes
do (remprop node 'neighbors)
(remprop node 'coordinates)))
(defun make-graph (arcs)
(let ((nodes (remove-duplicates (reduce (function append) arcs))))
(clear-graph nodes)
(dolist (arc arcs)
(push (second arc) (get (first arc) 'neighbors '())))))
Consider the graph built by:
(make-graph '((a b) (b c) (a d) (d e) (d f)))
and:
(depth-first 'a 'f)
(depth-first 'a 'c)
The search tree would be:
(a)
/ \
/ \
(a d) (a b)
| |
(a d e) (a b c)
|
(a d e f)
When walking the tree, queue would indeed contain paths that seems not
to be related, since we remove the root nodes. So for example, when
reaching (a d e), we will have printed:
(A)
(A D)
(A D E)
each path being the previous more one node.
Of course, this still is not entirely true, since if we are searching
c, when reaching (a d e f) we will then skip to (a b):
(A)
(A D)
(A D E)
(A D E F)
(A B)
(A B C)
Therefore that sentense is not true at all.
--
__Pascal Bourguignon__ http://www.informatimago.com/