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

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

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

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

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

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

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

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

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

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

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

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

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

12 問題の解決例 C B A

13 問題の解決例 C B A

14 問題の解決例 B C A

15 問題の解決例 B C A

16 問題の解決例 A B C

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

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

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

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

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

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

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

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

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

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

27 書換え問題の分解・還元 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

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

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

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

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

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

33 書換え問題の解 解 部分木 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

34 書換え問題の状態空間 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

35 書換え問題の解 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

36 書換え問題の解 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

37 積木の問題 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

38 積木の問題 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