Next: 4 状態空間探索による問題解決
Up: 3 ヒューリスティックな探索法
Previous: 3.5 最良優先探索法(best-first search)
これまでの探索手法ではqueueには可能性のあるものをすべて
保存するという形になっていました．しかし，枝分かれの多い場合や，
探索するレベルが深くなったりするとそのキューの大きさはかなり大きく
なってしまいます．そこで，必ずしもゴールへたどり着けるかどうか
わからないけれども，そのキューの範囲を限定するという方法で探索空間の
無駄を減らそうという方法がビーム探索と呼ばれるものです．
ビーム探索法は，最良優先探索におけるキューに対してある決まった段数を与
えることでその深さの探索しかしないということを行ないます．
(defun beam-search
(graph start goal beam-width)
(beam-search-aux graph start goal beam-width
(list (list start))))
(defun beam-search-aux
(graph start goal beam-width path-queue)
(let ((path (first path-queue)))
(cond
((null path-queue) nil)
((node-equal goal (first path)) (reverse path))
(t (beam-search-aux
graph start goal beam-width
(let ((sorted
(sort
(append
(new-paths path graph)
(rest path-queue))
#'(lambda (p1 p2) (closerp p1 p2 goal)))))
(if (> beam-width (length sorted))
sorted
(subseq sorted 0 beam-width))))))))
beam-widthを無限大にするとbest-first探索になります．
> (beam-search *graph1* 's 'f 1)
nil
> (beam-search *graph1* 's 'f 2)
(s a b e f)
> (beam-search *graph1* 's 'f 3)
(s a b e f)
subseqは以下のように部分列を取り出す関数です．
> (subseq '(a b c d e f) 0 2)
(a b)
> (subseq '(a b c d e f) 1 2)
(b)
> (subseq '(a b c d e f) 1 3)
(b c)
> (subseq '(a b c d e f) 2 3)
(c)
> (subseq '(a b c d e f) 2 2)
nil
>
generated through LaTeX2HTML. M.Inaba 平成18年5月6日