(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)))