7.4 横型探索(breadth-first search)

Next: 8 評価関数を用いる探索 Up: 7 グラフ探索 Previous: 7.3 縦型探索(depth-first search)

7.4 横型探索(breadth-first search)

横型探索とは，現在までに探索しているpathから新しいnew-pathsを得たあと，すでに蓄えておいたpath-queueの残りとをいっしょにする際に，new-queueの方を後回しにするということで実現されます．つまり新しい子どもの方ではなく，兄弟の方のpathを終えてから一段下の子どもを含んだpathを処理するわけである．横型の探索を行ないひとつのパスを返す関数breadth-first を以下に示す．ゴールのシンボルを直接渡すのではなく，ゴールかどうかを判定する手続きを渡すような形で定義すれば，

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

(defun breadth-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 (breadth-first-aux
          graph start goal
          (append
           (rest path-queue)
           (new-paths path graph))
          )))))

となり，再帰呼出をする際のpath-queueに渡す appendの引数の順をdepth-firstとは逆にするところだけが違いになる．

> (breadth-first *graph1* 's 'f)
(s d e f)
> (breadth-first *graph1* 's 'e)
(s d e)
> (breadth-first *graph1* 'f 's)
(f e d s)
> (breadth-first *graph1* 's 'c)
(s a b c)

ここでもわかるように，縦型探索の場合には，すぐ近くに目標値があっても隣接点リストの配置の如何によっては，遠回りの道が返る場合がありますが，横型では，必ず一番短い道がでてくる．しかし，枝分かれが多い場合には，その道にたどり着くまでに時間がかかることになる．

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