ヒューリスティック探索 ─ 知識に基づく探索 ─ (Heuristic Search) 最良優先探索 (best-first search) 均一コスト探索 欲張り最良優先探索 Ａ * 探索 ヒューリスティック関数について 最良優先探索の 具体的な例 認知システム論 探索（ 3 ） 先を読んで知的な行動を選択するエージェント.

Presentation on theme: "ヒューリスティック探索 ─ 知識に基づく探索 ─ (Heuristic Search) 最良優先探索 (best-first search) 均一コスト探索 欲張り最良優先探索 Ａ * 探索 ヒューリスティック関数について 最良優先探索の 具体的な例 認知システム論 探索（ 3 ） 先を読んで知的な行動を選択するエージェント."— Presentation transcript:

1 ヒューリスティック探索 ─ 知識に基づく探索 ─ (Heuristic Search) 最良優先探索 (best-first search) 均一コスト探索 欲張り最良優先探索 Ａ * 探索 ヒューリスティック関数について 最良優先探索の 具体的な例 認知システム論 探索（ 3 ） 先を読んで知的な行動を選択するエージェント

2 復習：一般的探索アルゴリズム TZ AR A S FO 必ず先頭から取り除 き 展開する 戦略に基づいて 適切な位置に挿入 B オープンリス ト F 展開する＝子を産む 未展開ノードはオープンリスト に並べる 子 子から親へ のポインタ

3 経路コストの導入 A Z O T L M D S R C P B G U H E V I N F 初期状態 ゴール 経路コス ト 151 75 71 140 118 111 70 75 99 80 146 120 97 101 138 90 85 98 86 142 92 87 211 最適解

4 T7T7 Z 10 A5A5 R 16 最良優先探索 (best-first search) O 15 B8B8 オープンリス ト 評価関数 (evaluation function) f(n) の小さい順になるよう挿入 評価値＞ 0 ベストに見えるも のを優先的に展開 評価関数の決め方によって いろいろなバリエーションが ある １．均一コスト探索 ２．欲張り最良優先探索 ３．Ａ * 探索

5 １．均一コスト探索 (uniform cost search) 初期状態からそのノード n までの経路コスト g(n) を評価関数とする最良優先探索 ゴールに向かって のシャープな探索 に なっていない g(n) = 5+3 = 8 a0a0 初期状態 35 b5b5 n8n8 現在状態 全オペレータのコスト＝１なら，幅優先探索と同じ動作 となる

6 均一コスト探索の実行 0 1 4 2 99 673 125 1 経路コスト g(n) の低い順に展開 オープンリス ト IN OUT 2 9 4 7 3 27 2 1 8 経路コスト g(n) の 昇順になるように 挿入 経路コス ト 1+2=3 オペレー タのコス ト

7 均一コスト探索の最適性 ただし，オペレータのコストは非負と する S A B C G startgoal 1 55 15 10 5 0 115 5 1 5 ABC S 1110 G G 5 展開のために選択した ときにゴールと判定す る 展開のために選択 してゴールと判定

8 均一コスト探索の性質 完全性 (completeness) あり 解があれば必ず見つける 最適性 (optimality) あり 最適解を最初に見つける 時間計算量 (time complexity) 指数的 ｂ d （ｂ：分枝率，ｄ： 解の深さ） 空間計算量 (space complexity) 指数的 ｂ d 幅優先探索 と同じ

9 ２． 欲張り最良優先探索 (greedy best-first search) a0a0 初期状態 35 b5b5 n8n8 現在状態 g h(n) ヒューリスティック関数 ノードからゴールまでの 最短経路コストの見積り これの小さい順に展開 そのノード n からゴールまでの予想コスト h(n) を評価関数とする最良優先探索 ゴール

10 ヒューリスティック (heuristic) と は？ 語源： アルキメデスが風呂で浮力の法 則を発見したときに叫んだ ” Heurika ! ” （ユーリカ！発見した！） 経験から発見した知識のこと 最悪ケースの性能は必ずしも上げないが， 平均的または典型的にはうまくいく手法

11 ヒューリスティック関数の例：直 線距離 A Z T S B 初期状態 ゴール 253 374 329 h(n) = ｎからゴールまでの直線距 離

12 欲張り最良優先探索は最適性がない A Z T S R P B F 329 253 374 366 178 193 0 80 97 101 211 99 h の値（直線距離） 最短経路はこちら！ （最適性がない） 欲張ってこっちにこだわった （欲張り最良優先探索） しかし多くの場合 うまくいく

13 欲張り最良優先探索は完全性がない A Z T S B 150 253 374 366 0 T1 T2 150 不適切なヒューリスティクス

14 欲張り最良優先探索の性質 完全性 (completeness) なし 解を見つけないことがある 最適性 (optimality) なし 最適解を見つける保証がない 時間計算量 (time complexity) ｂ ｍ （ ｍ： 探索木の最大の深さ） 空間計算量 (space complexity) ｂ ｍ 深さ優先探索 と同じ

15 ３． A* 探索 (A* search) 初期状態 35 n8n8 現在状態 h(n) ここから の予想コスト 経路全体の予想コスト f(n)=g(n)+h(n) をコスト関数とする最良優先探索 ゴール エイスター ここまで のコスト g(n) ｆ (n) = g(n) + h(n) n を経由する最短経路の見積もりコスト これの小さい順に展 開

16 許容的ヒューリスティック (admissible heuristic) A P R S B 初期状態 ゴー ル 253 実際の最小コスト h*(n) ＝ 278 予想最小コスト h(n) 直線距離 すべてのノードｎについて 予想最小コスト h(n) ≦ 実際の最小コスト h*(n) を満たすヒューリスティック関数のこと 楽観的 (optimistic) ヒューリスティッ ク とも言う

17 A* 探索の性質 完全性 (completeness) あり！ 解があれば必ず見つける 最適性 (optimality) 許容的（楽観的）ヒューリスティクスの場合， あり！ 最初に見つけた解は最適解 時間計算量 (time complexity) 空間計算量 (space complexity) ヒューリスティッ クの 精度に依存

18 経路コス ト h 関数の値 （直線距 離） 329 253 374 366 178 193 0 80 97 101 211 99 75 118 140 A S F R P B T 98 Z O 380 151 160 146 C 138 71 許容的ヒューリスティクスにより A* が最初に見つける解は最適解 450 B 366 449 447 393 413 415 418 417 329 253 374 366 178 193 0 80 97 101 211 99 75 118 140 A S F R P B T 98 Z 671 O 380 151 526 160 146 C 138 615 C 最適解

19 A ＊ アルゴリズムの最適性の証明 Sn G* G 最適解（コスト C* ） 非最適解 初期状態 OPEN リスト 探索木を成長させるアルゴリズムの動作から考えて， OPEN リストは常に，最適解の経路上にあるノードｎを少な くとも１つ含み，非最適解のゴールノード G と次の関係を満 たす． f(n) = g(n) + h(n) ≦ g(n) + h*(n) = C* < f(G) よって，必ず， G より先に n が OPEN リストから選ばれ て展開される．したがって， G は決して OPEN リストから 選ばれない． 探索木

20 最良優先探索の比較 均一コス ト 欲張りＡ*Ａ* 完全 ○ × ○ 最適 ○ × ○ 時間 × △△ 空間 × △△ 幅優先的深さ優先的 ヒューリスティ クス 次第 つねに h(n)=0 とすれば， A* は均一コスト探索と一致する． ただし，許容的 ヒューリスティッ ク

21 ヒューリスティック関数につ いて ヒューリスティックの優位性 ８パズルのヒューリスティッ ク ヒューリスティック関数の作 り方

22 ヒューリスティックの優位性 すべてのノード n において h 1 (n) ≦ h 2 (n) ≦ h*(n) 実際の 値 h 2 は h 1 より優位 h 2 で展開されたノー ド h 1 で展開されたノー ド ⊆

23 ８パズルのヒューリスティック関数 54 618 7 3 2 12 8 3 4 765 ゴール 初期状態 候補１ h 1 = ゴールの位置にないタイルの数．上の例で は７． 候補２ h 2 = 各タイルのゴール状態までのマンハッタン 距離の和．上の例では１８． ２＋３＋３ ＋３＋３ ＋２＋２ ＋４＋４ ＋２＋２ ＋０＋０ ＋２＋２ ＝１８ ■ どちらも許容的（楽観的） ■ h 2 は h 1 より優位．

24 ８パズルの実験結果 解の長さ 展開した平均ノード数 反復深化 A*(h 1 )A*(h 2 ) 21066 41121312 66802018 863843925 10471279339 1236440422773 143473941539113 161301211 183056363 207276676 22180941219 24391351641

25 ヒューリスティック関数の作り方 （１） 緩和問題 (relaxed problem) ＝ オペレータに対する制限を減らし て 解きやすくした問題 緩和問題の正確な解のコストが元の問題の 良いヒューリスティクスになっていることが多い ８パズルの場合： となりにタイルが置い てあってもそこに動か せる

26 ヒューリスティック関数の作り方 （２） A が B のとなり B が空 ＆ → A から B へタイル を動かせる 緩和問題の生成 A が B のとなり → A から B へタイル を動かせる → relax h1h1 h2h2 （無条件で）

27 ヒューリスティック関数の作り方 （３） h 1,h 2, …,h m という許容的ヒューリスティクスがあり， どれも他の優位にないとき，どれを選ぶか？ h(n) = max (h 1 (n), h 2 (n), …, h m (n) ) ■ ｈは許容的であり，かつ， 一つひとつの関数より優位

28 ヒューリスティック関数の作り方 （４） 状態の「特徴」の利用 h(n)=α× 駒の得点の差 ＋ β× 駒の働きの差 ＋ γ× 玉の囲いの差 将棋の例 α β γ ： 機械学習アルゴリズムで値を調整す る 膨大な量のナマ情報を 適切に要約した少量の情報

29 450 366 449 447 393 413 415 418 417 526 615 付録： A* 探索の振る舞い（１） 単 調性 探索木に沿ったすべての経路 で f のコストは非減少 しかし，すべての問題で単調性が成り立つわけではない．

30 付録： A* 探索の振る舞い（２） 単調性 の定義 n' n ゴー ル h(n) h(n') c(n,n') 単調性 三角不等式に 似ている 先へ進んで，情報が得られてくるほど，楽観性が弱 くなる

31 450 366 449 447 393 413 415 418 417 526 615 付録： A* 探索の振る舞い（３） 等 高線 A* アルゴリズムは f 値の山を ゴールに向かって，見落とし なく （シャープに）単調に登って いく f = 366 の等高線 393413415417418 準最適解 最適解の等高線 最適性あり！ 完全性あり！ 実際には，単調性がなくても，最適性と完全性があ る．