10.2.2 全パスの探索

Next: 10.2.3 目標頂点までの全パスを探索する Up: 10.2 探索木の生成 Previous: 10.2.1 パスの展開

10.2.2 全パスの探索

探索木において末端までのすべてのパスを返す関数 find-all-pathsは以下のように定義可能です．


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

行なっていることは，path-queueに，これからまだチェックしなければならないpathのリストを与えます． pathの先頭に隣接し，すでにpathの中に含まれている頂点を除いた new-nodesを求め，それがなにもなければ探索木の末端（葉）にきているということで，その時のpathを根が先頭に来るように並べ変えて（reverse)残りの path-queueに対してfind-all-pathsしたものに加えます． new-nodesがある場合には，残りのpath-queueにnew-pathsを加え合わせ (append)たあたらしいpath-queueを作り，find-all-pathsを呼びます．

<cl> (setq *tree1* (find-all-paths *graph1* 's))
((S D E F) (S D E B C) (S D E B A)
 (S D A B E F) (S D A B C) (S A D E F)
 (S A D E B C) (S A B E F)
 (S A B E D) (S A B C)) 
<cl> (find-all-paths *graph2* 's)
((S A B C) (S A B E D) (S A B E F)
 (S A D E B C) (S A D E F) (S D A B C)
 (S D A B E F) (S D E B A)
 (S D E B C) (S D E F)) 
<cl> (find-all-paths *graph3* 's)
((S A B C) (S A B E D) (S A B E F)
 (S A D E B C) (S A D E F) (S D A B C)
 (S D A B E F) (S D E B A)
 (S D E B C) (S D E F))

同一の頂点から得られるneighborsはいつも変わりませんが，new-nodesの方は現在のpathに依存して変わってしまうため，各頂点に付加的にこのnew-nodes 情報を覚えておかずに，path-queueの中にpathの形でどんどん付け加えるという方法をとっています．path-queueがなくなれば，再帰的にpathデータを作りつつ戻ります．

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