lisp - 关于 Winston 和 Horn 在 "Lisp"中的问题 19-2 的问题

Question

Winston 和 Horn states 的“Lisp”中的问题 19-2，

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))

但是，我不明白这是怎么回事。例如，我得到输出像下面这样:

(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) 

我在例程开头放置打印语句的地方:

(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)))))) 

在这种情况下，队列中没有部分路径是扩展一个队列中它之后的部分路径的节点。这是练习中的打印错误还是有一些输入居然给了他给的队列？

Answer 1

参见 answer Pascal Bourguignon 着。