next up previous
Next: 10.3 親子関係を表す木表現の生成 Up: 10.2 探索木の生成 Previous: 10.2.2 全パスの探索

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

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

(defun find-all-goal-paths
  (graph start goal-p
            &optional (path-queue (list (list start))))
  (let ((path (first path-queue)))
    (cond
     ((null path-queue) nil)
     ((funcall goal-p (first path))
      (cons
       (reverse path)
       (find-all-goal-paths graph start goal-p
                            (rest path-queue))))
     (t (find-all-goal-paths
         graph start goal-p
         (append (new-paths (new-nodes path graph) path)
                 (rest path-queue)))))))
find-all-goal-pathsでは，goal-pという目標に達成したかどうかを判断する 述語関数を与えます．pathの先頭の頂点がその述語に与えられ目標状態かどう かが判断されます．ここでは，頂点はシンボルで表現されているため，目標頂 点とeqで等しいかどうかという関数を与えることになります．この目標が達成 されたらば，そのpathを返します． 目標が達成されていなくて，探索木の葉に来たところで，そこまでのpathは無 視して残りのpath-queueをfind-all-goal-pathsに渡します． 以下のように働きます． 
<cl> (find-all-goal-paths *graph4* 's (is 'f))
((S A B E F) (S A D E F) (S D A B E F) (S D E F)) 
<cl> (find-all-goal-paths *graph6* 's (is 'f))
((S A B E F) (S A D E F) (S D A B E F) (S D E F)) 
<cl> (find-all-goal-paths *graph5* 'f (is 's))
((F E D A S) (F E D S) (F E B A D S) (F E B A S)) 
<cl> (find-all-goal-paths *graph2* 's (is 'd))
((S A B E D) (S A D) (S D))
isは， 
(defun is (x) #'(lambda (y) (eq x y)))
関数を返す関数です．(is 'f)というのは f と等しいかどうかを判定する 関数を作ります．
generated through LaTeX2HTML. M.Inaba 平成18年5月6日