Next: 6.3 積み木問題の探索
Up: 6 状態空間の生成
Previous: 6.1 状態遷移操作の抽出
現在の状態から可能な次の状態のリストを作りだすために，まず
possible-statesという関数を作ります．
possible-statesは，現在の状態state，
移動するブロックおよびそのブロックを載せる対象
のリストdestを与えて次の状態の
リストを返すとします．
> s
((a on table) (b on c) (c on table) (d on a))
> (possible-states 'd s '(b table))
(((d on b) (a on table) (b on c) (c on table))
((d on table) (a on table) (b on c) (c on table)))
> (possible-states 'b s '(d table))
(((b on d) (a on table) (c on table) (d on a))
((b on table) (a on table) (c on table) (d on a)))
> (possible-states 'a s '(b d))
(((a on b) (b on c) (c on table) (d on a))
((a on d) (b on c) (c on table) (d on a)))
> (possible-states 'a s '(b d table))
(((a on b) (b on c) (c on table) (d on a))
((a on d) (b on c) (c on table) (d on a))
((a on table) (b on c) (c on table) (d on a)))
> (possible-states 'b s '(b d table))
(((b on b) (a on table) (c on table) (d on a))
((b on d) (a on table) (c on table) (d on a))
((b on table) (a on table) (c on table) (d on a)))
> (possible-states 'c s '(b d table))
(((c on b) (a on table) (b on c) (d on a))
((c on d) (a on table) (b on c) (d on a))
((c on table) (a on table) (b on c) (d on a)))
> (possible-states 'a s '(a b c d table))
(((a on a) (b on c) (c on table) (d on a))
((a on b) (b on c) (c on table) (d on a))
((a on c) (b on c) (c on table) (d on a))
((a on d) (b on c) (c on table) (d on a))
((a on table) (b on c) (c on table) (d on a)))
> (possible-states 'b s '(a b c d table))
(((b on a) (a on table) (c on table) (d on a))
((b on b) (a on table) (c on table) (d on a))
((b on c) (a on table) (c on table) (d on a))
((b on d) (a on table) (c on table) (d on a))
((b on table) (a on table) (c on table) (d on a)))
> (possible-states 'c s '(a b c d table))
(((c on a) (a on table) (b on c) (d on a))
((c on b) (a on table) (b on c) (d on a))
((c on c) (a on table) (b on c) (d on a))
((c on d) (a on table) (b on c) (d on a))
((c on table) (a on table) (b on c) (d on a)))
> (possible-states 'd s '(a b c d table))
(((d on a) (a on table) (b on c) (c on table))
((d on b) (a on table) (b on c) (c on table))
((d on c) (a on table) (b on c) (c on table))
((d on d) (a on table) (b on c) (c on table))
((d on table) (a on table) (b on c) (c on table)))
> (possible-states 'table s '(a b c d table))
(((table on a) (a on table) (b on c) (c on table) (d on a))
((table on b) (a on table) (b on c) (c on table) (d on a))
((table on c) (a on table) (b on c) (c on table) (d on a))
((table on d) (a on table) (b on c) (c on table) (d on a))
((table on table) (a on table) (b on c) (c on table) (d on a)))
(defun possible-states (block state dest)
(let*
((current (assoc block state))
(other (remove current state)))
(node-remove
current
(mapcar
#'(lambda (d)
(cons (list block 'on d) other))
dest))))
以上の手続きを組み合わせることで，現在の状態を与えると，可能な次の
状態を作り出す手続きnext-blocks-statesを考えます．
> s
((a on table) (b on c) (c on table) (d on a))
> (next-blocks-states s)
(((b on table) (a on table) (c on table) (d on a))
((b on d) (a on table) (c on table) (d on a))
((d on table) (a on table) (b on c) (c on table))
((d on b) (a on table) (b on c) (c on table)))
> (next-blocks-states
'((a on table) (b on c) (c on table)))
(((a on b) (b on c) (c on table))
((b on table) (a on table) (c on table))
((b on a) (a on table) (c on table)))
> (next-blocks-states
'((a on table) (b on c) (c on table) (d on a)))
(((b on table) (a on table) (c on table) (d on a))
((b on d) (a on table) (c on table) (d on a))
((d on table) (a on table) (b on c) (c on table))
((d on b) (a on table) (b on c) (c on table)))
(defun next-blocks-states
(state)
(let ((top-free
(top-free-blocks state)))
(node-remove
state
(mapcan
#'(lambda (free-block)
(possible-states
free-block
state
(cons 'table
(remove free-block top-free))))
top-free)))))
generated through LaTeX2HTML. M.Inaba 平成18年5月6日