人工知能 探索（3） 先を読んで知的な行動を選択するエージェント 知識を用いる探索 ─ ヒューリスティック探索 ─ (Heuristic Search) 最良優先探索 均一コスト探索 欲張り探索 Ａ* 探索 最良優先探索の 具体的な例 ヒューリスティック関数について 復習：一般的探索アルゴリズム 展開する＝子を産む 未展開ノードは待ち行列に並べる A 待ち行列 子から親への ポインタ 必ず先頭から取り除き 展開する F 子 S A T O Z R 戦略に基づいて 適切な位置に挿入 B 経路コストの導入 初期状態 71 O 75 Z 経路コスト N 151 140 A 118 F R 70 P 146 M 75 D ゴール 97 L 120 V 211 最適解 111 I 92 99 S 80 T 87 85 U 98 B 101 138 C 142 90 G H 86 E 最良優先探索(best-first search) 待ち行列 A 5 T 7 コスト ＞0 ベストに見えるものを 優先的に展開 Z 10 O 15 R 16 コスト関数(cost function) の小さい順になるよう挿入 B 8 コスト関数の決め方によって いろいろなバリエーションがあ る １．均一コスト探索 ２． 欲張り探索 ３． Ａ* 探索 １．均一コスト探索(unform cost search) 初期状態からそのノードn までの経路コスト g(n) をコスト関数とする最良優先探索 初期状態 a 0 5 ゴールに向かって のシャープな探索に なっていない 現在状態 b 5 3 n 8 g(n) = 5+3 = 8 全オペレータのコスト＝１なら，幅優先探索と同じ動作となる 均一コスト探索の実行 オペレー タのコスト 0 経路コスト g(n) の低い順に展開 4 1 経路コス ト 1+2=3 9 12 1 2 3 2 5 4 1 7 9 待ち行列 2 2 7 3 6 7 9 IN OUT 8 経路コスト g(n) の 昇順になるように 挿入 均一コスト探索の最適性 ただし，オペレータのコストは非負とする S A start S 1 10 5 B 15 5 5 C goal G 1 A G 1 10 11 B 0 15 C 5 G 5 15 5 10 展開のために選択 してゴールと判定 展開のために選択したと きにゴールと判定する 均一コスト探索の性質 最適性(optimality) あり 最適解を最初に見つける 完全性(completeness) あり 解があれば必ず見つける 時間計算量(time complexity) 指数的 ｂd （ｂ：分枝率，ｄ：解の深さ） 空間計算量(space complexity) 指数的 ｂd 幅優先探索 と同じ ２．欲張り探索(greedy search) そのノードnからゴールまでの予想コスト h(n) をコスト関数とする最良優先探索 初期状態 a 0 5 現在状態 b 5 3 ヒューリスティック関数 ノードからゴールまでの 最短経路コストの見積り これの小さい順に展開 n 8 h(n) ゴール g ヒューリスティック(heuristic)とは？ 語源： アルキメデスが風呂で浮力の法則を 発見したときに叫んだ”Heurika !” （ユーリカ！ 発見した！） 経験から発見した知識のこと 最悪ケースの性能は必ずしも上げないが，平 均的にはたいていの場合はうまくいく手法 ヒューリスティック関数の例：直線距離 初期状態 Z A T 374 h(n) = ｎからゴールまでの直線距離 S 329 253 ゴール B 欲張り探索は最適解を見つける保証がない h の値（直線距離） Z 欲張ってこっちにこだわった 374 253 A S 366 T 329 （欲張り探索） 99 F 178 しかし多くの場合 うまくいく 80 193 R 最短経路はこちら！ （最適性がない） 97 211 P 101 B 0 欲張り探索は解を見つける保証（完全性）がない Z 374 A 366 T 150 T1 150 T2 150 253 S 不適切なヒューリスティクス B 0 欲張り探索の性質 最適性(optimality) なし 最適解を見つける保証がない 完全性(completeness) なし 解を見つけないことがある 時間計算量(time complexity) ｂｍ （ｍ： 探索木の最大の深さ） 空間計算量(space complexity) ｂｍ 深さ優先探索 と同じ エイスター ３．A* 探索(A* search) 経路全体の予想コスト f(n)=g(n)+h(n) （ただし，h(n)は許容的なヒューリスティック関数） をコスト関数とする最良優先探索 初期状態 n 5 3 現在状態 8 g(n) h(n) ここまでのコスト ゴール ここからの予想コスト ｆ(n) = g(n) + h(n) n 経由の最短経路の見積もりコスト これの小さい順に展開 許容的ヒューリスティック(admissible heuristic) 予想最小コスト h(n) ≦ 実際の最小コスト h*(n) を満たすヒューリスティック関数のこと 初期状 態 A 楽観的(optimistic) ヒューリスティック とも言う 予想最小コスト h(n) S 253 直線距離 ゴール R 実際の最小コスト h*(n)＝278 P B ヒューリスティクスが許容的と限らないときは，Aアルゴリズムと呼ぶ． A* 探索の性質 最適性(optimality) あり！ 最初に見つけた解は最適解 完全性(completeness) あり！ 解があれば必ず見つける 時間計算量(time complexity) 空間計算量(space complexity) ヒューリスティックの 精度に依存 A*が最初に見つける解は最適解 経路コスト O Z 71 75 449 374 A 366 366 140 118 T 447 329 526 380 151 S h 関数の値 （直線距離） 393 253 F 99 417178 80 R 413 193 211 97 P B 415 98 B 450 146 101 418 0 C 526 138 160 C 615 最適解 160 A*探索の振る舞い（１） 単調性 526 449 366 探索木に沿ったすべての経路で f のコストは非減少 393 447 417 413 415 526 615 450 418 しかし，すべての問題が単調性が成り立つわけではない． A*探索の振る舞い（２） 単調性の定義 単調性 h(n) h(n ') c(n, n ') 三角不等式に 似ている 先へ進んで，情報が得られてくるほど，楽観性が弱くなる h(n ') h(n) c(n, n ') n h(n) c(n,n') ゴール n' h(n') A*探索の振る舞い（３） 等高線 449 f = 366 の等高線 366 A*アルゴリズムは f 値の山を ゴールに向かって，見落としなく （シャープに）単調に登っていく 526 393 413 415 393 447 418 417 413 最適解の等高線 準最適解 415 最適性あり！ 完全性あり！ 417 526 615 実際には，単調性がなくても，最適性と完全性がある． 450 418 最良優先探索の比較 均一コスト 欲張り Ａ* 完全 ○ × ○ 最適 ○ × ○ 時間 × △ △ 空間 × △ △ 幅優先的 深さ優先的 ヒューリスティクス 次第 つねに h(n)=0 とすれば，A*は均一コスト探索と一致する． ヒューリスティック関数について ヒューリスティックの優位性 ８パズルのヒューリスティック ヒューリスティック関数の作り方 ヒューリスティックの優位性 ≦ h2(n) ≦ h*(n) h2 は h1 より優位 h1 で展開されたノード ⊆ すべてのノード n において h1(n) 実際の 値 h2 で展開されたノード ８パズルのヒューリスティック関数 初期状態 候補１ 1 5 4 6 1 8 8 7 3 2 7 2 3 ゴール 4 6 5 h1=ゴールの位置にないタイルの数．上の例では７． 候補２ h2=各タイルのゴール状態までのマンハッタン距離 の和．上の例では１８． ２ ＋３ ＋３ ＋２ ＋４ ＋２＋０ ＋２ ＝１８ ■どちらも許容的（楽観的） ■h2はh1より優位． ８パズルの実験結果 解の長さ 展開した平均ノード数 反復深化 A*(h1) A*(h2) 2 10 6 6 4 112 13 12 6 680 20 18 8 6384 39 25 10 47127 93 39 12 364404 227 73 14 3473941 539 113 16 1301 211 18 3056 363 20 7276 676 22 18094 1219 24 39135 1641 ヒューリスティック関数の作り方（１） 弱条件問題 ＝ オペレータに対する制限を減らして 緩和問題 解きやすくした問題 (relaxed problem) ８パズルの場合： となりにタイルが置いて あってもそこに動かせる 弱条件問題の正確な解のコストが元の問題の 良いヒューリスティクスになっていることが多い ヒューリスティック関数の作り方（２） 弱条件問題の自動生成 AがBのとなり ＆ Bが空 relax AがBのとなり → AからBへタイル を動かせる h2 h1 Bが空 → AからBへタイル を動かせる → AからBへタイル を動かせる ヒューリスティック関数の作り方（３） h1,h2,…,hm という許容的ヒューリスティクスがあり， どれも他の優位にないとき，どれを選ぶか？ h(n) = max (h1(n), h2(n), …, hm(n) ) ■ ｈは一つひとつの関数より優位 ヒューリスティック関数の作り方（４） 統計情報の利用 h2(n)=14 → 90%の確率で実際の距離＝18 許容性の保証はなくなるが 平均的に効率が向上する h(n)=18 ヒューリスティック関数の作り方（５） 状態の「特徴」の利用 将棋の例 h(n)=α×駒の得点の差 ＋β×駒の働きの差 ＋γ×玉の囲いの差 α β γ：学習アルゴリズムで値を調整する
© Copyright 2024 ExpyDoc
