COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Q about Problem 19-2 in "Lisp" by Winston and Horn

• Email
• Follow

```Problem 19-2 in "Lisp" by Winston and Horn states, "In depth-first
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?
```
 0
Reply paul.reiners (11) 8/28/2010 7:10:54 PM

See related articles to this posting

```Paul Reiners <paul.reiners@gmail.com> writes:

> Problem 19-2 in "Lisp" by Winston and Horn states, "In depth-first
> 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?

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/
```
 0
Reply pjb 8/28/2010 8:40:34 PM

1 Replies
308 Views

Similar Articles

12/10/2013 9:45:02 PM
page loaded in 66655 ms. (0)

Similar Artilces:

Problems building CLISP 2.35 on OS X?
Has anyone but me had any trouble building CLISP on an OS X (10.4) machine? I grabbed the CVS sources today and tried to build them and it died with this message: stream.d: In function 'rl_memory_abort': stream.d:15068: error: 'rl_gnu_readline_p' Undeclared (first use in this function) make[1]: *** [stream.o] Error 1 make: *** [staging/clisp-2.35/src/clisp] Error 2 Anyone know what this is about? -Peter P.S. I realize that this would be better addressed to the CLISP developers list but the moderator of that list rejected my message when I tried to post it there via ...

forth abstraction vs lisp macroes
can forth build up abstractions such as lisp macroes can? are there some kind fo techniques ? ...

Statistics for comp.lang.lisp #79
Following is a summary of articles spanning a 7 day period, beginning at 20 Feb 2005 07:53:38 GMT and ending at 27 Feb 2005 06:46:59 GMT. Notes ===== - A line in the body of a post is considered to be original if it does *not* match the regular expression /^\s{0,3}(?:>|:|\S+>|\+\+|\|\s+|\*\s)/. - All text after the last cut line (/^-- \$/) in the body is considered to be the author's signature. - The scanner prefers the Reply-To: header over the From: header in determining the "real" e-mail address and name. - Original Content Rating is th...