next up previous
Next: 9.6 ビーム探索法(beam search) Up: 9 見込み探索 Previous: 9.4 山登り法(hill-climb search)

9.5 最良優先探索法(best-first search)

新しいノードとすでに保存してあるノードのすべての中から もっとも可能性の高そうなものの順に並べ替えるという処理 を行なう． 
(defun best-first
  (graph start goal)
  (best-first-aux graph start goal
                  (list (list start))))

(defun best-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 (best-first-aux
          graph start goal
          (sort
           (append
            (new-paths path graph)
            (rest path-queue))
           #'(lambda (p1 p2)
               (closerp p1 p2 goal))))))))

> (best-first *graph1* 's 'f)
(s a b e f)

> (best-first *graph1* 'f 's)
(f e d s)

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