第８回　 問題解決.

Presentation on theme: "第８回　 問題解決."— Presentation transcript:

1 第８回　 問題解決

2 問題解決 とは 具体例： ・鶴と亀が合わせて7匹 ・足の合計は２０本 ・鶴と亀は各々何匹いる？
x+y=7, 2x+4y=20 ⇒ (x,y)=(4,3)

3 問題解決のプロセス 問題の定式化： 対象となる世界（外部世界）から本質的な部分を抽出し，形式的記述を獲得
問題の定式化：　 対象となる世界（外部世界）から本質的な部分を抽出し，形式的記述を獲得 形式的処理： 形式的記述を形式的に処理して解を抽出 　　（内部世界） 問題の対象となる世界での解釈： 問題の対象となる世界での解を確保

4 問題の定式化 状態空間法 問題分解法 手段目的解析 （ Means End Analysis ）

5 状態空間法：解探索の定式化 状態空間中を初期状態から目標状態（解）に至る径路を探索すること ・状態空間（state space)：
　状態を節点(node)、状態遷移を有向枝（arc)としたグラフで表現 ・オペレータ： 　状態遷移のための手段　 ～　前提条件、削除リスト、追加リスト ・拘束条件： 　目標達成のために守らねばならない条件　

6 迷路探索の例 拘束条件： 左向き進行 　禁止

7 解探索の基本手法 縦型探索 深さ優先探索(depth-first search) 深さ方向を優先的に展開
　深さ方向を優先的に展開 横型探索 幅優先探索(breadth-first search) 　初期節点からの径路が浅い節点を優先的に展開

8 解探索の基本手法（模式図） 親節点 子節点

9 基本手法の比較 縦型探索 - 停止しない危険性あり ←深さ方向に制限 - 最適解に到達する保証無し - メモリ消費量は少ない 横型探索
縦型探索 - 停止しない危険性あり　←深さ方向に制限 - 最適解に到達する保証無し - メモリ消費量は少ない 横型探索 - 径路長最短の解に到達する保証あり - メモリ消費量は多い

10 解探索の効率化 問題固有の知識利用 - 枝のコスト： ２地点間の距離、経費、・・
問題固有の知識利用　 - 枝のコスト：　２地点間の距離、経費、・・ 　- 節点評価値：　目標節点への近さ 　 ～　ヒューリスティクス関数 　- 合併評価 探索手続きの改良 　- 山登り法　(hill-climbing method) 　- 分枝限定法 (branch-and bound method)

11 Ａ＊アルゴリズム Ａアルゴリズム: 最良優先探索の改良　～ 現局面（節点）から解に至るまでの予測評価h(n)に 出発点から現局面までの評価g(n)を加味 　 f(n) = g(n) + h(n) Ａ＊アルゴリズム 　 f(n) = g(n) + h’(n) 　h’(n) ≦h(n) ；楽観的なヒューリスティクス関数 最適解への到達を保証→ＡＩにおける代表的な探索方式

12 Ａ＊アルゴリズムの例：８-パズル h’(n)： ゴール状態と異なる位置におかれたタイル数
h’(n) ≦h(n)：　ゴールまでに動かさないといけないタイル数

13 ８-パズルの解法

14 山登り法 現在吟味中の節点に対し、基本操作を施し到達できる次状態候補（現節点の子節点）の中で最も評価値の高い節点を選択 （局所的最適化）
・縦型探索 ・最適解の保証は無し

15 分枝限定法 山登り法の改良 ～ 現節点の子節点に限定せず、これまでに展開されながら利用されていない節点のうち最適な ものを選択
山登り法の改良　～ 　現節点の子節点に限定せず、これまでに展開されながら利用されていない節点のうち最適な ものを選択 ・オペレーションズリサーチ(OR)における 組合せ最適化問題にて提案された手法と同一 ・横型探索の改良型

16 分枝限定法による探索の例 S – [C(1), B(2)] – [B(2), F(4), H(5)] –
[D(3), E(4), F(4), H(5)] – [E(4), F(4), H(5), G1(5), I(6)]-

17 最良優先探索(best-first search)
現局面（節点）から解に至るまでの予測評価h(n)をヒューリスティクス関数として与え、利用 ・目標まで到達可能 ・大容量メモリが必要 ・最適解に到達する保証無し

18 ビーム探索(beam search) 最良優先探索で評価値の高いほうからＮ個、
またはしきい値以上のもののみ残すことに より、メモリの増大を抑制 ・最適解に到達する保証無し

19 ゲーム木の探索 ～ 囲碁・将棋 vs. チェス，チェッカー，オセロ，バックギャモン
ミニ・マックス法：相手は最小値，自分は 最大値の手を選択→α-β法 最大評価の際の 下限以外をカット 最小評価の際の 上限以外をカット

20 問題分解法 個々の状態空間が持つ構造を利用して 探索を行う
～　より簡単な部分問題(sub goal)に分割，解が自明な問題(原始問題：principle)になるまで反復 対象）・数式処理（不定積分，因数分解，・・） 　　　　・ゲーム（オセロ，・・）

21 部分問題への分解例 問題：１つ200円のりんごと１つ100円のナシを 合わせて６つ買い，800円を支払った． りんごとナシを幾つずつ買ったか？ 問題の定式化：　 　ｘ＋ｙ＝６，　２００ｘ＋１００ｙ＝８００ 副問題１： 　２００ｘ＋１００（６－ｘ）＝８００ 　ただし　ｙ＝６－ｘ 副問題２： 　２００ （６－ｙ） ＋１００ｙ＝８００ 　ただし　ｘ＝６－ｙ

22 AND/OR グラフによる記述 節点： 問題 または 部分問題 - AND節点： 全て充足することを要求
節点：　問題　または　部分問題 　- AND節点：　全て充足することを要求 - OR節点：　一つでも充足すればＯＫ 　- 終端節点：　直ちに解決できる問題 枝：　親問題と部分問題の関係 Ｃｆ）状態空間法～ 　節点：状態，枝：オペレータによる状態遷移 問題を解くこと： AND/ORグラフの中から，条件を満足する 解グラフを求めること

23 AND/OR グラフによる記述例１：食事の支度
食事：　主食と副食とお茶 　～　部分問題に分割 副食：　魚料理と肉料理 プロダクション規則 ・主食→米を炊く ・主食→ご飯を温める ・魚料理→魚を焼く　かつ　野菜を煮る ・肉料理→肉を炒める　かつ　野菜をゆでる

24 AND/OR グラフ表現：　食事の支度 AND節点 OR節点 解グラフの例 「夕食を食べる」？

25 例２：　不定積分 解決の候補）　 ・部分積分法 ・置換積分法：　 ・漸化式

26 不定積分問題のAND/OR表現 OR分解 AND分解

27 例３： ３目並べ 3x3の盤面に黒石，白石を持つプレーヤーが交互に石を置き，先に縦・横・斜めに３つ連続して 並べた方が勝ち
例３：　３目並べ 3x3の盤面に黒石，白石を持つプレーヤーが交互に石を置き，先に縦・横・斜めに３つ連続して 並べた方が勝ち お互い最善を尽くすと引き分け ・自分の手番：　ＯＲ分岐 ～可能手から最善手を選択 ・相手の手番：　ＡＮＤ分岐 ～相手の打つ全ての手を検討 白 黒 白

28 ３目並べの例 〈自分：　黒） X:　必敗手 × ×

29 Means End Analysis (MEA)
以下の処理を反復 現在の状態を目標状態と比較 差異を減少させる操作を選択 可能ならその操作を適用．可能でなければ現在の状態を退避，部分問題に適用 部分問題が解決されたら退避した問題を回復，解探索作業を再開

30 MEAにおけるヒューリスティクス知識 以下の関数として実現 ２つの状態の間の差異を計算する関数
与えられた差異の解消に貢献する操作を選択する関数 解として許される操作の系列に関する 制約

31 コスト関数 初期状態S0, O1(So)=S1, O2(S1)= S2, ・・ となる操作系列｛Ｏｉ｝： f(p) =
　となる操作系列｛Ｏｉ｝： f(p) = が最小となる系列を求める