next up previous
Next: 5.4 状態表現の一般化 Up: 5.3 探索手続き Previous: 5.3.1 迷路の探索

5.3.2 積み木の問題解決

以下のようにパスを求めることが可能となる． 
> (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月7日