Next: 6.5 積み木での最終手続き
Up: 6 状態空間の生成
Previous: 6.3 積み木問題の探索
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))
generated through LaTeX2HTML. M.Inaba 平成18年5月6日