next up previous
Next: 13.3 親子関係を表す木表現の生成 Up: 13 探索木 Previous: 13.1 探索木の生成

13.2 目標頂点までの全パスを探索する

あるグラフから探索木を作った場合，目標頂点までにいたるパスが複数存在す ることはあり得る．そこで，ある頂点から別の頂点への道すべてを拾いあげ る関数は，find-all-pahsを参考にして以下のように作ることができる． 
(defun find-all-goal-paths
  (graph start goal)
  (find-all-goal-paths-aux graph start goal
                           (list (list start))))

(defun find-all-goal-paths-aux
  (graph start goal path-queue)
  (let ((path (first path-queue)))
    (cond
        ((null path-queue) nil)
      ((equal goal (first path))
       (cons
        (reverse path)
        (find-all-goal-paths-aux graph start goal
                             (rest path-queue))))
      (t (find-all-goal-paths-aux
          graph start goal
          (append (new-paths path graph)
                  (rest path-queue)))))))
ここでは， 目標が達成されていなくて，探索木の葉に来たところで，そこまでのpathは無 視して残りのpath-queueをfind-all-goal-pathsに渡す． 
> (setq *tree1* (find-all-goal-paths *graph1* 's 'f))
((s d e f) (s d a b e f) (s a d e f) (s a b e f))

> (find-all-goal-paths *graph1* 'f 's)
((f e b a s) (f e b a d s) (f e d s) (f e d a s))

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