5.2 積木問題の記述

Next: 5.3 探索手続き Up: 5 状態空間探索による問題解決 Previous: 5.1 迷路問題の記述

5.2 積木問題の記述

積木の世界の問題は，図6に示すように，問題のなかに現れる状態は１３通りであることがわかる．図では，このそれぞれにシンボルを割り振っている．この問題の解く場合に，各状態にわりつけたシンボルで問題を解くとこれまでにも例を示してきた探索と同様に解くことが可能となる．しかし，その場合，シンボルがどのような状態のものをさしているかということを解いたことにはなっていないことに注意する必要がある．そこで，それぞれの状態での個々の積木の状態を記述するための記述子として

( 物 on 物またはtable)

というものを考え，それぞれの状態を表現することにする．

**図 6:** 積木の世界の状態空間
$\includegraphics[width=8.5cm]{/home/inaba/eps/lecture/fig/blockstates.eps}$

> *blocks-graph*
 ((((a on table) (b on table) (c on table))
   ((a on table) (b on c) (c on table)))
  (((a on table) (b on table) (c on table))
   ((a on table) (b on a) (c on table)))
  (((a on table) (b on table) (c on table))
   ((a on c) (b on table) (c on table)))
  (((a on table) (b on table) (c on table))
   ((a on b) (b on table) (c on table)))
  (((a on table) (b on table) (c on table))
   ((a on table) (b on table) (c on b)))
  (((a on table) (b on table) (c on table))
   ((a on table) (b on table) (c on a)))
  (((a on table) (b on c) (c on table))
   ((a on b) (b on c) (c on table)))
  (((a on table) (b on c) (c on table))
   ((a on table) (b on a) (c on table)))
  (((a on table) (b on a) (c on table))
   ((a on table) (b on a) (c on b)))
  (((a on c) (b on table) (c on table))
   ((a on c) (b on a) (c on table)))
  (((a on c) (b on table) (c on table)))
   ((a on b) (b on table) (c on table)))
  (((a on b) (b on table) (c on table))
   ((a on b) (b on table) (c on a)))
  (((a on table) (b on table) (c on b))
   ((a on c) (b on table) (c on b)))
  (((a on table) (b on table) (c on b))
   ((a on table) (b on table) (c on a)))
  (((a on table) (b on table) (c on a))
   ((a on table) (b on c) (c on a))))

これは，

(defun blocks-graph nil
  (let ((s1 '((a on table) (b on table) (c on table)))
	(s11 '((b on table) (a on table) (c on table)))
        (s2 '((a on table) (b on c)     (c on table)))
        (s3 '((a on table) (b on a)     (c on table)))
        (s4 '((a on c)     (b on table) (c on table)))
        (s5 '((a on b)     (b on table) (c on table)))
        (s6 '((a on table) (b on table) (c on b)))
        (s7 '((a on table) (b on table) (c on a)))
        (s8 '((a on b)     (b on c)     (c on table)))
        (s9 '((a on table) (b on a)     (c on b)))
        (s10 '((a on c)    (b on a)     (c on table)))
        (s11 '((a on b)    (b on table) (c on a)))
        (s12 '((a on c)    (b on table) (c on b)))
        (s13 '((a on table) (b on c)    (c on a))))
    (setq *blocks-graph*
          (list
           (list s1 s2)
           (list s1 s3)
           (list s1 s4)
           (list s1 s5)
           (list s1 s6)
           (list s1 s7)
           (list s2 s8)
           (list s2 s3)
           (list s3 s9)
           (list s4 s10)
           (list s4 s5)
           (list s5 s11)
           (list s6 s12)
           (list s6 s7)
           (list s7 s13)))))

により作られる．

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