Next: 11 積木問題の状態空間の生成 Up: ソフトウェア第三　講義資料行列，リスト操作，グラフ，探索表現 Previous: 9.6 ビーム探索法(beam search)

10 状態空間の生成

問題解決において，状態空間をグラフとしてあらかじめ与えることができるならば，単なる探索手続きを実行すればよいが，その状態空間をグラフとして記述して与えるのではなく，ある状態からある状態へ遷移する手続きを与える形で状態空間を間接的に表現できれば，より現実的な問題解決に適用できることになる．たとえば，上に上げた積木の問題において，積み木が４つ，５つ，というように数が異なれば，*blocks-graph*に状態空間となるグラフをあらかじめ作って与えることが必要となる方法であった．しかし，そのようなグラフを積木の数が異なる場合にすべて記述しつくしておいて問題を解くのはそれほどうれしいものではない．そこで，グラフ全体を与えずとも探索する手法が必要となる．積み木の問題にかぎらず，一般的な状態空間探索法の構造として，最終的には，


(motion-planning start goal)

というようなmotion-planning手続きにより，初期状態start から最終状態へ至る動作命令の列を生成する関数が使えるようにするには，

(node-equal s1 s2): ある状態 s1 とある状態 s2 が同じ状態かどうかを調べる
(next-states s) : ある状態 s から遷移可能な次の状態のリスト
(goal-search s g) : 初期状態 s と目標状態 g を与える探索戦略に応じた探索手続き
(node-operation s1 s2) : ある状態 s1 から次の状態 s2 へ移る操作命令を返す

という基本手続きを構成すればよい．ただし，new-nodes, motion-planningは以下のように定義しておく必要がある．

(defun new-nodes (path graph)
  (remove-if
   #'(lambda (n) (node-member n path))
   (next-states (first path))))

(defun operations-from-path (state-path)
  (let* ((state (pop state-path))
         (result nil))
    (dolist (s state-path)
      (setq result
        (cons (node-operation state s)
              result))
      (setq state s))
    (reverse result)))

(defun motion-planning
  (start goal)
  (operations-from-path
   (goal-search start goal)))

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