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

Next: 3 ヒューリスティックな探索法 Up: 2 評価関数を利用する道の探索 Previous: 2.3 パスの長さ

2.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月6日