11.4 goal-searchの定義

Next: 11.5 node-operationの定義 Up: 11 積木問題の状態空間の生成 Previous: 11.3 next-statesの定義

11.4 goal-searchの定義

next-blocks-states は，ノードとなるステートを引数としているいわばadjacency-listを返す．

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

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

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

図11のような４つの積木の場合の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)))

ということで，goal-searchは，


(defun goal-search (s g)
  (depth-first nil s g))

(defun goal-search (s g)
  (breadth-first nil s g))

のように定義できる．

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