Next: 11.1 状態遷移可能性の判断 Up: ソフトウェア第三　講義資料行列，リスト操作，グラフ，探索表現 Previous: 10 状態空間の生成

11 積木問題の状態空間の生成

**図 10:** ４つの積木の場合
$\includegraphics[width=5cm]{/home/inaba/eps/lecture/fig/blocks4states.eps}$

ある状態をすべてのブロックが何の上にあるかという状態の列で与えることにする．たとえば，a,b,c,dの４つのブロックがある場合の１つの状態は， ((a on table) (b on c) (c on table) (d on a)) という形で表する．このような場合に，この状態を与えて，その中に含まれるすべてのブロック名を返す関数 all-blocksと，与えられた状態の中で上に何も載っていないブロックを返す関数 top-free-blocksを次のように定義できる．

> (all-blocks '((a on table) (b on a)))
(A B) 
> (top-free-blocks '((a on table) (b on a)))

(B) 
> (top-free-blocks
           '((a on table) (b on table)))

(A B) 

> (setq s
   '((a on table) (b on c) (c on table) (d on a)))
((a on table) (b on c) (c on table) (d on a))

> (all-blocks s)
(b c a d)

> (top-free-blocks s)
(b d)

(defun all-objects (state)
  (cond
   ((null state) nil)
   (t (union (remove 'on (car state))
             (all-objects (cdr state)))))
  )

(defun all-blocks (state)
  (remove 'table (all-objects state)))

(defun top-free-blocks
  (state)
  (let ((blocks (all-blocks state)))
    (dolist
        (x state)
      (if (not (eq 'table (third x)))
          (setq blocks (remove (third x) blocks))))
    blocks))

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