問題解決 問題の表現 定性的，論理的関係を対象とした問題 問題解決プロセスの表現 状態空間 問題の分解・還元

問題の表現 [記号] 　　　：リンゴの個数 　　　：ナシの個数 1個200円のリンゴと1個100円のナシを合わせて6個買い，800円支払いました．　　　　　リンゴとナシはそれぞれ何個買ったでしょうか？ [定量的関係]

問題の表現 [記号] 太郎は花子の父であり,次郎は太郎の父である．父の父は祖父である．花子の祖父は誰か？ ： は の父である 　　　　 ：　 は　 の父である 　　　 ：　 は　 の祖父である 太郎は花子の父であり,次郎は太郎の父である．父の父は祖父である．花子の祖父は誰か？ [論理的関係]

問題の別表現 リンゴの個数 ナシの個数 合計 6 600 1 5 700 2 4 800 3 900 1000 1100 1200 1個200円のリンゴと1個100円のナシを合わせて6個買い，800円支払いました．　　　　　リンゴとナシはそれぞれ何個買ったでしょうか？

積木の世界の表現 積木の状態の表現 A C B B A C 初期状態 目標状態

積木の世界の表現 ロボットの手の状態の表現 B C C B A A

基本的操作の表現（１） 　を持ち上げる 前提条件 削除リスト 追加リスト C B C C B A A B A

基本的操作の表現（１） 　を　　の上に置く 前提条件 削除リスト 追加リスト B B C C C A B A A

基本的操作の表現（２） 基本的操作 前提条件 削除リスト 追加リスト

基本的操作の表現（２） 基本的操作 前提条件 削除リスト 追加リスト

問題の解決例 初期状態 C B A

問題の解決例 C B A

問題の解決例 C B A

問題の解決例 B C A

問題の解決例 B C A

問題の解決例 A B C

問題の解決例 目標状態 A B C

問題解決に必要な知識 問題領域に関する知識 解決方法に関する知識 事実や状態の記述 （例：積木の状態の記述） データ 問題領域に関する知識 事実や状態の記述　（例：積木の状態の記述） 関係や規則の記述　（例：基本的操作の記述） 解決方法に関する知識 演算，操作，戦略などに関する知識 アルゴリズム

問題解決プロセスの表現 状態空間の探索 　　　　　　　　探索木 問題の分解・還元 　　　　　　　　AND/OR木　

状態空間 問題 状態空間 A B C G S D ＃１ ＃２ ＃３ ＃４ ＃６ ＃８ ＃５ ＃７ 規則 前提条件 追加リスト ＃１ S A

状態空間の探索 状態空間→探索木 S ＃１ ＃２ ＃３ A B ＃６ ＃５ ＃４ C ＃８ ＃７ G D

状態空間の探索 状態空間→探索木 S 初期状態 S ＃１ ＃２ A B ＃３ A B B G C ＃６ ＃５ A ＃４ C C D G ＃８ ＃７ D G G G D 目標状態

状態空間の探索 状態空間→探索木 S 初期状態 S ＃１ ＃２ A B ＃３ A B B G C ＃６ ＃５ A ＃４ C C D G ＃８ ＃７ D G G G D 目標状態

問題の分解・還元 問題 副問題 副問題 OR

問題の分解・還元 問題 部分問題 部分問題 AND

書換え問題 問題 「文字列 “ABC”を以下の書換規則を用いて文字列“Z･･･Z”に書き換えることができるか？」 書換規則 ① A → XY ②　A　→　BZ ③　B　→　X　 ④　B　→　Z ⑤　C　→　BBZ

書換え問題の分解・還元 AND/OR木 ABC A B C XY BZ X Z BBZ X Y B Z B B Z X Z X Z X Z “ABC”を “ZZ･･･Z”に書き換える問題 AND/OR木 ABC ① A→XY ② A→BZ ③ B→X ④ B→Z ⑤ C→BBZ A B C XY BZ X Z BBZ X Y B Z B B Z X Z X Z X Z

書換え問題の解 解の探索 ABC A B C XY BZ X Z BBZ X Y B Z B B Z X Z X Z X Z

書換え問題の解 解の探索 ABC A B C XY BZ X Z BBZ X Y B Z B B Z X Z X Z X Z

書換え問題の解 解の探索 ABC A B C XY BZ X Z BBZ X Y B Z B B Z X Z X Z X Z

書換え問題の解 解の探索 ABC A B C XY BZ X Z BBZ X Y B Z B B Z X Z X Z X Z

書換え問題の解 解の探索 ABC A B C XY BZ X Z BBZ X Y B Z B B Z X Z X Z X Z

書換え問題の解 解 部分木 ABC A B C BZ Z BBZ B Z B B Z Z Z Z ・②→④ ・④ ・⑤→④ ②→⑤→④ ① A→XY ② A→BZ ③ B→X ④ B→Z ⑤ C→BBZ A B C ② ④ ⑤ ・②→④ ・④ ・⑤→④ BZ Z BBZ B Z B B Z ②→⑤→④ ④ ④ ④ ②→④→⑤→④ Z Z Z

書換え問題の状態空間 ABC XYBC BZBC AXC AZC ABBBZ XYXC XYZC XYBBBZ XZXC ZZZC ① A→XY ② A→BZ ③ B→X ④ B→Z ⑤ C→BBZ ABC ① ③　 ④ ⑤ ② XYBC BZBC AXC AZC ABBBZ ③ ⑤ ③ ④ ④ ⑤ XYXC XYZC XYBBBZ XZXC ZZZC BZBBBZ ④ ⑤ ③ ZZZBBZ XZXXXZ ZZZZZZ ③ ④ ZZZXXZ ZZZZZZ

書換え問題の解 ABC XYBC BZBC AXC AZC ABBBZ XYXC XYZC XYBBBZ XZXC ZZZC BZBBBZ ① A→XY ② A→BZ ③ B→X ④ B→Z ⑤ C→BBZ ABC ① ③　④　⑤ ② ②→⑤→④ XYBC BZBC AXC AZC ABBBZ ③ ⑤ ③ ④ ④ ⑤ XYXC XYZC XYBBBZ XZXC ZZZC BZBBBZ ④ ⑤ ③ ZZZBBZ XZXXXZ ZZZZZZ ③ ④ ④ ZZZXXZ ZZZZZZ

書換え問題の解 ABC XYBC BZBC AXC AZC ABBBZ XYXC XYZC XYBBBZ XZXC ZZZC BZBBBZ ① A→XY ② A→BZ ③ B→X ④ B→Z ⑤ C→BBZ ABC ① ③　④　⑤ ② XYBC BZBC AXC AZC ABBBZ ③ ⑤ ③ ④ ④ ⑤ XYXC XYZC XYBBBZ XZXC ZZZC BZBBBZ ④ ⑤ ③ ②→④→⑤→④ ZZZBBZ XZXXXZ ZZZZZZ ③ ④ ④ ZZZXXZ ZZZZZZ

積木の問題 A A B B C C on(A,B) & on(B,C) on(A,B) on(B,C) holding(B) STACK(B,C) holding(B) clear(C) PICKUP(B) ontable(B) clear(B) empty UNSTACK(A,B) on(A,B) clear(A) empty

積木の問題 A A B B C C on(A,B) & on(B,C) on(A,B) on(B,C) holding(B) STACK(B,C) PUTDOWN(A) holding(B) clear(C) holding(A) PICKUP(B) ontable(B) clear(B) empty UNSTACK(A,B) on(A,B) clear(A) empty