Next: 13.2 目標頂点までの全パスを探索する
Up: 13 探索木
Previous: 13 探索木
探索木の生成というのは，出発頂点が与えられ，すでに通った頂点を通らない
ように道を探すため，現在の位置までのpathを覚えつつ道を探すということを
行なう必要がある．出発時点では，pathはその出発点のみ含んだpathが一
つである．そして，その出発点に隣接する頂点があればその現在までのpathをそ
の隣接点まで伸ばす．その際，隣接点が複数あることもあるため，複数の
pathを生成する必要がある．そして探索を進めてゆくのは，その複数の
pathをすべて保持した形で進めてゆく必要がある．
ひとつのパスをシンボルのリストで表現し，探索木のすべてのパスを
調べて，そのパスのリストで表現するというものを考える．
すなわち，根を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 b c) (s a b e d)
(s a b e f) (s a b c))
のように表せる．
この探索木をグラフから生成する手続き
find-all-pathsは以下のように定義可能である．
(defun find-all-paths
(graph start)
(find-all-paths-aux graph start (list (list start)))
)
(defun find-all-paths-aux (g s path-queue)
(if
(null (car path-queue)) nil
(let ((nn (new-nodes (car path-queue) graph)))
(if
(null nn)
(cons (reverse (car path-queue))
(find-all-paths-aux graph start
(cdr path-queue)))
(find-all-paths-aux
graph start
(append
(new-paths nn (car path-queue))
(cdr 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を呼ぶ．
> (find-all-paths *graph1* 's)
((s d e b a) (s d e b c) (s d e f)
(s d a b e f) (s d a b c) (s a d e b c)
(s a d e f) (s a b e f) (s a b e d) (s a b c))
> (find-all-paths *graph1* 'f)
((f e b a s d) (f e b a d s) (f e b c)
(f e d s a b c) (f e d a s) (f e d a b c))
同一の頂点から得られるneighborsはいつも変わらないが，new-nodesの方は
現在のpathに依存して変わってしまうため，各頂点に付加的にこのnew-nodes
情報を覚えておかずに，path-queueの中にpathの形でどんどん付け加えるとい
う方法をとる．path-queueがなくなれば，再帰的にpathデータを作りつつ戻る．
generated through LaTeX2HTML. M.Inaba 平成18年5月7日