next up previous
Next: 7.4 横型探索(breadth-first search) Up: 7 グラフ探索 Previous: 7.2 パスの展開

7.3 縦型探索(depth-first search)

find-all-pathsでは，隣接点リストに入っている頂点の順に調べてゆくという 方法をとっていた．これは，探索木の深さ方向にどんどん調べてゆき末端 の葉が来たところで，ひとつ前の頂点で枝わかれしたところまでのpathから得 られる別のpathsを調べるという方法であった．このような探索方法は縦型探索 と呼ばれる． この縦型探索に基づいて目標頂点へたどり着く道を ひとつ探す関数が以下に示すdepth-firstである． 
(defun node-equal (a b) (equal a b))

(defun depth-first
  (graph start goal)
  (depth-first-aux graph start goal
                   (list (list start))))

(defun depth-first-aux (graph start goal path-queue)
  (let ((path (first path-queue)))
    (cond
        ((null path-queue) nil)
      ((node-equal goal (first path)) (reverse path))
      (t (depth-first-aux
          graph start goal
          (append
           (new-paths path graph)
           (rest path-queue))
          )))))
という具合に再帰的に定義をしたり， 
(defun depth-first*
  (graph start goal)
  (let* ((path (list start))
         (path-queue (list path)))
    
    (catch 'depth-first
      (while
          path-queue
        (cond
            ((node-equal goal (first path))
             (throw 'depth-first (reverse path)))
          (t
           (setq path-queue
                 (append
                  (new-paths path graph)
                  (rest path-queue)))
           (setq path (car path-queue))))))))
というように繰り返し文で 定義することも可能です． 
> (depth-first* *graph1* 's 'f)
(s d e f)
> (depth-first* *graph1* 'f 's)
(f e b a s)
以下のような実行結果が得られる． 
> (setq *graph1*
        '((s a) (s d) (a b) (a d)
          (b c) (b e) (d e) (e f)))

((s a) (s d) (a b) (a d) (b c) (b e) (d e) (e f))

> (setq *graph2* '((f e) (e b) (e d) (d s)
         (d a) (c b) (b a) (a s)))

((f e) (e b) (e d) (d s) (d a) (c b) (b a) (a s))

> (depth-first *graph1* 's 'f)
(s d e f)
> (depth-first *graph2* 's 'f)
(s a d e f)
> (depth-first *graph1* 'f 's)
(f e b a s)
> (depth-first *graph2* 'f 's)
(f e d a s)

> (depth-first *graph1* 'd 's)
(d s)
> (depth-first *graph2* 'd 's)
(d e b a s)

> (depth-first* *graph1* 's 'f)
(s d e f)
> (depth-first* *graph2* 's 'f)
(s a d e f)
> (depth-first* *graph1* 'f 's)
(f e b a s)
> (depth-first* *graph2* 'f 's)
(f e d a s)
> (depth-first* *graph1* 'd 's)
(d s)
> (depth-first* *graph2* 'd 's)
(d e b a s)
*graph1*と*graph2*とでは，隣接点リストの順番が 異なることになるため返ってくるパスが異なっている． letとlet*の違いは， 
> (setq a '(1 2 3 4 5 6))
(1 2 3 4 5 6)

> (let ((a 1) (b a)) (list a b))
(1 (1 2 3 4 5 6))

> (let* ((a 1) (b a)) (list a b))
(1 1)
という違いがある．
generated through LaTeX2HTML. M.Inaba 平成18年5月7日