6.3 積み木問題の探索

Next: 6.4 移動操作の生成 Up: 6 状態空間の生成 Previous: 6.2 状態遷移可能性の判断

6.3 積み木問題の探索

グラフを探索する手続き graph-search*を用いて，以下のような block-searchを作ります． next-blocks-states は，ノードとなるステートを引数としているいわばadjacency-listを返します．


(defun new-nodes (path graph)
  (remove-if
   #'(lambda (n) (node-member n path))
   (next-blocks-states (first path))))

という具合に定義すれば，

**図 9:** ４つの積木の場合の問題
$\includegraphics[width=8cm]{/home/inaba/eps/lecture/fig/blocks4task.eps}$

図9のような４つの積木の場合のstart状態からgoal状態への縦型探索と横型探索を実行してみると以下のようになります．


> (depth-first nil
      '((b on c) (a on b) (c on table))
      '((a on table) (b on c) (c on a)))

(((b on c) (a on b) (c on table))
 ((a on table) (b on c) (c on table))
 ((b on table) (a on table) (c on table))
 ((c on b) (b on table) (a on table))
 ((c on a) (b on table) (a on table))
 ((b on c) (c on a) (a on table)))

> (breadth-first nil
     '((a on b) (b on table) (c on d) (d on table))
     '((a on table) (b on a) (c on table) (d on c)))

(((a on b) (b on table) (c on d) (d on table))
 ((a on table) (b on table) (c on d) (d on table))
 ((b on a) (a on table) (c on d) (d on table))
 ((c on table) (b on a) (a on table) (d on table))
 ((d on c) (c on table) (b on a) (a on table)))

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