8.4 分枝限定法(branch-and-bound search)

Next: 9 見込み探索 Up: 8 評価関数を用いる探索 Previous: 8.3 パスの長さ

8.4 分枝限定法(branch-and-bound search)

次の頂点を決めるために，path-queueに溜っているものすべてに対して path-lengthを計算して一番短いものを選択するという方法である．

(defun branch-and-bound
  (graph start goal)
  (branch-and-bound-aux graph start goal
                        (list (list start))))

(defun branch-and-bound-aux
  (graph start goal path-queue)
  (let ((path (first path-queue)))
    (cond
        ((null path-queue) nil)
      ((node-equal goal (first path))
       (reverse path))
      (t (branch-and-bound-aux
          graph start goal
          (sort
           (append
            (new-paths path graph)
            (rest path-queue))
           #'shorterp))))))


> (branch-and-bound *graph1* 's 'f)
(s d e f)

sortを使っていますが，実はすべてを並べ替える必要はない．もっとも評価の高いもののみを一つ選ぶという処理でも十分である．各パスのコストがもっとも短くなる解を必ず見つけるのがこの分岐限定法である．ちなみに，ならべ替えを行う手続きsortの実行例を示しておく．


> (sort '(1 3 2 5 4) #'<)
(1 2 3 4 5)

> (sort '(1 3 2 5 4) #'>)
(5 4 3 2 1)

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