next up previous
Next: 11.6 積木の問題における基本関数 Up: 11 積木問題の状態空間の生成 Previous: 11.4 goal-searchの定義

11.5 node-operationの定義

block-searchが返す結果は,状態の列で,実際にどのブロックをどこ からどこへ動かすという形の表現の方が分かりやすい.そこで,この探索結果 から(move block from place1 to place2)という形の動作コマンドの列へ変換 する手続きを作ることを考える. まず,一手順で遷移可能であることが保障されているstate1からstate2へ 移るための手続きblock-operationを定義する. それには,集合の差をとる演算set-を定義して, ステート記述の差をとることで行ってみる.
(defun block-operation
  (state1 state2)
  (let ((s2 (car (set- state2 state1)))
	(s1 (car (set- state1 state2))))
    (list 'move (car s2)
          'from (elt s1 2)
          'to (elt s2 2))))
これ以外にも,
(defun block-operation
  (state1 state2)
  (let ((blocks (all-blocks state1)))
    (catch 'block-operation
      (dolist
          (b blocks)
        (let ((s1 (assoc b state1))
              (s2 (assoc b state2)))
          (when
              (not (node-equal s1 s2))
            (throw 'block-operation
                   `(move ,b from ,(caddr s1)
                          to ,(caddr s2)))))))))
という形で書くこともできる. これを用いて,状態の列を与えて動作 コマンド列を返す手続きblock-operationsを定義する.
(defun block-operations (state-path)
  (let* ((state (pop state-path))
         (result nil))
    (dolist (s state-path)
      (setq result
        (cons (block-operation state s)
              result))
      (setq state s))
    (reverse result)))
> (block-operation
  '((d on c) (c on table) (b on table) (a on table))
  '((b on a) (d on c) (c on table) (a on table)))

(move b from table to a)
block-operationsを前の探索結果に適用した場合の結果は 次のようになる.
> (block-operations
'(((a on b) (b on table) (c on d) (d on table))
 ((a on table) (b on table) (c on d) (d on table))
 ((b on a) (a on table) (c on d) (d on table))
 ((c on table) (b on a) (a on table) (d on table))
 ((d on c) (c on table) (b on a) (a on table))) )

((move a from b to table)
 (move b from table to a)
 (move c from d to table)
 (move d from table to c))


> (block-operations
 '(((a on b) (b on table) (c on d) (d on table))
 ((a on table) (b on table) (c on d) (d on table))
 ((b on a) (a on table) (c on d) (d on table))
 ((c on table) (b on a) (a on table) (d on table))
 ((b on table) (c on table) (a on table) (d on table))
 ((a on b) (b on table) (c on table) (d on table))
 ((a on c) (b on table) (c on table) (d on table))
 ((a on d) (b on table) (c on table) (d on table))
 ((b on a) (a on d) (c on table) (d on table))
 ((b on c) (a on d) (c on table) (d on table))
 ((a on table) (b on c) (c on table) (d on table))
 ((b on d) (a on table) (c on table) (d on table))
 ((c on a) (b on d) (a on table) (d on table))
 ((b on table) (c on a) (a on table) (d on table))
 ((c on b) (b on table) (a on table) (d on table))
 ((d on a) (c on b) (b on table) (a on table))
 ((c on table) (d on a) (b on table) (a on table))
 ((d on b) (c on table) (b on table) (a on table))
 ((d on c) (c on table) (b on table) (a on table))
 ((b on a) (d on c) (c on table) (a on table))) 
)

((move a from b to table)
 (move b from table to a)
 (move c from d to table)
 (move b from a to table)
 (move a from table to b)
 (move a from b to c)
 (move a from c to d)
 (move b from table to a)
 (move b from a to c)
 (move a from d to table)
 (move b from c to d)
 (move c from table to a)
 (move b from d to table)
 (move c from a to b)
 (move d from table to a)
 (move c from b to table)
 (move d from a to b)
 (move d from b to c)
 (move b from table to a))
結局積み木の問題は,ある状態から,ある状態を作るために,どのような動作 列が必要かを示す手続きが必要で,それをfinalに渡すことで求める結果を得 ることができる.たとえば,横型探索を用いるとすると,
(defun block-motion-sequence
  (start goal)
  (block-operations
   (breadth-first nil start goal)))
という具合に記述ができる.
> (block-motion-sequence
     '((a on b) (b on table) (c on d) (d on table))
     '((a on table) (b on a) (c on table) (d on c)))

((move a from b to table)
 (move b from table to a)
 (move c from d to table)
 (move d from table to c))

> (block-motion-sequence
       '((c on table) (a on table) (b on table))
       '((b on table) (a on b) (c on a)))

((move a from table to b)
 (move c from table to a))

> (block-motion-sequence
      '((b on table) (a on b) (c on a))
      '((c on table) (a on table) (b on table)))

((move c from a to table)
 (move a from b to table))
という具合になる.

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