5.4 状態表現の一般化

Next: 6 グラフ Up: 5 状態空間探索による問題解決 Previous: 5.3.2 積み木の問題解決

5.4 状態表現の一般化

積木の例での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

このようになって，パスがないという答えが返ってくる．それは当然であり，状態が同じかどうかを判定するところでこの状態表現へ対応していないからである．そこで，ここでグラフの頂点の比較はリスト表現されたものの集合であるということから，集合が等しいかどうかを判定する関数set=を使って，二つのノード状態が等しいかどうかを判定する基本関数を以下のように，


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

と定義する．ただし，今の場合，この集合の要素を比較する関数はeqではだめで，equalでなければならない．このようにすれば，

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

という結果になり，無事探索が成功する．このように，問題空間の表現をシンボル，リスト，集合で表すことが可能であるが，それぞれにおいて状態が同じかどうかを判定する手続きnode-equalを定義しなおせば同じ探索手続きを用いることができる．

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