Next: 6 状態空間の生成 Up: ソフトウェア特論講義資料グラフ探索，問題解決 Previous: 4.2 積木問題の記述

5 状態の集合表現

上に上げた例での*s8*は((a on b) (b on c) (c on table))という状態ですが，これは意味としては３つの積木の状態の集合ですから，その要素の順番はこの順である必要はありません．そこで，((b on c) (a on b) (c on table))というように最初の順番を変えて与えてみると，


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

nil

このようになって，パスがないという答えが返ってきてしまいます．それは当然であって，node-equalに与える関数がequalだからです．そこで，ここでグラフの頂点の比較はリスト表現されたものの集合であるということから，集合が等しいかどうかを判定する関数set=を使って，


(defun node-equal (a b) (set= a b))

と定義します．


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

という結果になり，無事探索が成功しました．

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