14.2 探索木の生成

Next: 14.3 縦型，横型探索 Up: 14 探索プログラムの実現 Previous: 14.1 グラフの表現

14.2 探索木の生成

探索木を作るメソッドを:find-all-pathsとしてgraphクラスに定義する．self 変数に:find-all-pathsを送ることで再帰定義がなされている．


(defun new-nodes (path)
  (remove-if
   #'(lambda (n) (member n path))
   (node-neighbors (first path))))

(defun new-paths (new-nodes path)
  (mapcar
   #'(lambda (n) (cons n path))
   new-nodes))

;;;
(defmethod find-all-paths
    ((self graph) start
     &optional (path-queue (list (list start))))
  (if
      (null path-queue) nil
    (let* ((path (first path-queue))
           (new-nodes (new-nodes path)))
      (if
          (null new-nodes)
          (cons (reverse path)
                (find-all-paths self
                                start
                                (rest path-queue)))
        (find-all-paths
         self
         start
         (append (new-paths new-nodes path)
                 (rest path-queue)))))
    ))

実行結果は以下のようになります．


<cl> (find-all-paths *graph* (find-node *graph* "s"))
((#<NODE @ #x203c1a92> #<NODE @ #x203c1ac2>
  #<NODE @ #x203c1af2> #<NODE @ #x203c1b22>)
 (#<NODE @ #x203c1a92> #<NODE @ #x203c1ac2>
  #<NODE @ #x203c1af2> #<NODE @ #x203c1b82>
  #<NODE @ #x203c1b52>)
 (#<NODE @ #x203c1a92> #<NODE @ #x203c1ac2>
  #<NODE @ #x203c1af2> #<NODE @ #x203c1b82>
  #<NODE @ #x203c1bb2>)
 (#<NODE @ #x203c1a92> #<NODE @ #x203c1ac2>
  #<NODE @ #x203c1b52> #<NODE @ #x203c1b82>
  #<NODE @ #x203c1af2> #<NODE @ #x203c1b22>)
 (#<NODE @ #x203c1a92> #<NODE @ #x203c1ac2>
  #<NODE @ #x203c1b52> #<NODE @ #x203c1b82>
  #<NODE @ #x203c1bb2>)
 (#<NODE @ #x203c1a92> #<NODE @ #x203c1b52>
  #<NODE @ #x203c1ac2> #<NODE @ #x203c1af2>
  #<NODE @ #x203c1b22>)
 (#<NODE @ #x203c1a92> #<NODE @ #x203c1b52>
  #<NODE @ #x203c1ac2>
  #<NODE @ #x203c1af2> #<NODE @ #x203c1b82>
  #<NODE @ #x203c1bb2>)
 (#<NODE @ #x203c1a92> #<NODE @ #x203c1b52>
  #<NODE @ #x203c1b82>
  #<NODE @ #x203c1af2> #<NODE @ #x203c1ac2>)
 (#<NODE @ #x203c1a92> #<NODE @ #x203c1b52>
  #<NODE @ #x203c1b82> #<NODE @ #x203c1af2>
  #<NODE @ #x203c1b22>)
 (#<NODE @ #x203c1a92> #<NODE @ #x203c1b52>
  #<NODE @ #x203c1b82> #<NODE @ #x203c1bb2>))

generated through LaTeX2HTML. M.Inaba 平成18年5月6日