next up previous
Next: 2 評価関数を利用する道の探索 Up: 1 探索戦略 Previous: 1.1 縦型探索(depth-first search)

1.2 横型探索(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月6日