next up previous
Next: 5 状態の集合表現 Up: 4 状態空間探索による問題解決 Previous: 4.1 迷路問題の記述

4.2 積木問題の記述

積木の世界の問題は,図7に示すように, 問題のなかに現れる状態は13通りであることがわかります. 図では,このそれぞれにシンボルを割り振っています. このような問題の状態空間の解析を行なったあとに問題を解くことを考えると, この問題を解決するプログラムは探索プログラムを適用することで実現可能と なります. この問題の解く場合に,各状態にわりつけたシンボルで 問題を解くとこれまでにも例を示してきた探索と同様に解くことが 可能となります.しかし,その場合,シンボルがどのような状態のものを さしているかということを解いたことにはなっていないことに 注意する必要があります. そこで,それぞれの状態での個々の積木の状態を記述する ための記述子として
( 物 on 物またはtable)
というものを考え,それぞれの状態を表現することにします.
図 7: 積木の世界の状態空間
\includegraphics[width=8.5cm]{/home/inaba/eps/lecture/fig/blockstates.eps}

(defun blocks-graph nil
  (let ((s1 '((a on table) (b 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 s5 s11)
           (list s6 s12)
           (list s6 s7)
           (list s7 s13)))))
関数blocks-graphにより出来上がった リスト*blocks-graph*は, 以下のように状態空間を辺で表現した形に なっています.

> *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 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))))
以下のようにパスを求めることが可能となります.

> (depth-first *blocks-graph*
      '((a on b) (b on c) (c on table))
      '((a on table) (b on c) (c on a)))
(((a on b) (b on c) (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 table) (c on a))
 ((a on table) (b on c) (c on a)))

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

(((a on b) (b on c) (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 table) (c on a))
 ((a on table) (b on c) (c on a)))
状態としてリスト表現を与えるのではなく, 状態を表現したシンボル変数を与えても 結果は同じです.

(setq *s1*
      '((a on table) (b on table) (c on table)))
(setq *s1a*
      '((b on table) (a on table) (c on table)))
(setq *s2* '((a on table) (b on c) (c on table)))
(setq *s3* '((a on table) (b on a) (c on table)))
(setq *s4* '((a on c) (b on table) (c on table)))
(setq *s5* '((a on b) (b on table) (c on table)))
(setq *s6* '((a on table) (b on table) (c on b)))
(setq *s7* '((a on table) (b on table) (c on a)))
(setq *s8* '((a on b) (b on c) (c on table)))
(setq *s9* '((a on table) (b on a)     (c on b)))
(setq *s10* '((a on c)    (b on a) (c on table)))
(setq *s11* '((a on b)    (b on table) (c on a)))
(setq *s12* '((a on c)    (b on table) (c on b)))
(setq *s13* '((a on table) (b on c)    (c on a)))

> (depth-first *blocks-graph* *s8* *s13*)

(((a on b) (b on c) (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 table) (c on a))
 ((a on table) (b on c) (c on a)))

> (breadth-first *blocks-graph*
                *s8* *s13*)

(((a on b) (b on c) (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 table) (c on a))
 ((a on table) (b on c) (c on a)))


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