代码不太理解, 望高手解释 breadth-first search in lisp

homme1986

急求哪位熟悉common lisp的朋友能把下面breadth-first search 代码解释下, 特别是有下划线的部分. nodes-not-visited 这段function没贴出来,可以忽略. 另外根据实际问题写了生成tree的代码, 但不知道下面的代码中哪里可以调用?

(defstruct bfs-node state parent)

(defun bfs-graph (start &optional verbose)         ;; ??
  (let ((node-list (list (make-bfs-node :state start :parent nil))))
     (do*((node (car node-list) (car node-list))
                  (closed nil)
                  (goal-found (if (goal-state? start) node nil)))       ;;"gola-state?"是用来比较的吗?在哪定义的?
            ((or (null node-list) goal-found)
               (if (null node-list)
               "No solution."
               (extract-bfs-path goal-found)))
      (when verbose (format t "Expanding node ~d~%" (bfs-node-state node)))
      (let* ((all-succs (mapcar #'(lambda (e) (make-bfs-node :state e :parent node))
                                           (expand (bfs-node-state node))))        ;; expand 是变量吗? 后面那部分是赋值吗?
                             (succs (nodes-not-visited all-succs node-list closed)))
               (setq goal-found (find-if #'(lambda (s) (goal-state? (bfs-node-state s))) succs))
               (setq node-list (append (cdr node-list) succs))
               (setq closed (cons node closed))))))

(defun extract-bfs-path (node)        ;; 生成tree的代码在哪里调用?
  (do ((path nil)
       (n node (bfs-node-parent n)))
      ((null n) path)
    (setq path (cons (bfs-node-state n) path))))

win_hate

1、&optional 说明后面的参数 verbose 是可选的

2、goal-start? 是函数，在某处定义

3、expand 是函数，后面不是赋值

4、作用在 tree 上的函数肯定于 tree 的结构有关。你说 tree 已经生成，但不知到怎么引用这棵 tree？

homme1986

谢谢版主解答!!

可能我没说清楚. 我在做一些关于AI的作业, 像是 water-jug, 8-queen problem. 现在已经根据规则把对初始变量(例如 (0 0))expand的代码写好了, 但是不知道在上面search代码中哪里进行调用.

另外代码中的node, closed, goal-found 应该是变量吧? "(or (null node-list) goal-found)" 这段代码有什么用?

[ 本帖最后由 homme1986 于 2009-4-25 09:23 编辑 ]