Next: 8 迷路問題への適用 Up: ソフトウェア特論講義資料グラフ探索，問題解決 Previous: 6.5 積み木での最終手続き

7 統一的状態空間探索手続きの構造

積み木の問題にかぎらず，一般的な状態空間探索法の構造として，


(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)))

というような手続きを用意して，最終的には， motion-planningという手続きである状態から次の状態へ移る動作命令の列を生成する関数が使えるようにするには，

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

というような手続きを構成すればよいことになります．積み木の問題では，


(defun node-equal (a b) (set= a b))

(defun next-states (state)
  (next-block-states state))

(defun node-operation
  (state1 state2)
  (block-operation state1 state2))

(defun goal-search (s g)
  (breadth-first nil s g))

という具合な設定になります．

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