next up previous
Next: 9.5 最良優先探索法(best-first search) Up: 9 見込み探索 Previous: 9.3 ヒューリスティック関数

9.4 山登り法(hill-climb search)

現在の頂点から次の候補の頂点を展開した時に， その展開したものの中でもっともゴールに近そうな ものを次の探索コースと決める方法である． 
(defun hill-climb
  (graph start goal)
  (hill-climb-aux graph start goal
                  (list (list start))))

(defun hill-climb-aux
  (graph start goal path-queue)
  (let ((path (first path-queue)))
    (cond
        ((null path-queue) nil)
      ((node-equal goal (first path)) (reverse path))
      (t (hill-climb-aux
          graph start goal
          (append
           (sort
            (new-paths path graph)
            #'(lambda (p1 p2) (closerp p1 p2 goal)))
           (rest path-queue)))))))

> (hill-climb *graph1* 's 'f)
(s a b e f)

> (path-length '(s a b e f))
19.9137144

> (hill-climb *graph1* 'f 's)
(f e d s)

> (path-length '(f e d s))
13.0735922

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