Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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

1 ヒューリスティック探索 ─ 知識に基づく探索 ─ (Heuristic Search) 最良優先探索 (best-first search) 均一コスト探索 欲張り最良優先探索 A * 探索 ヒューリスティック関数について 最良優先探索の 具体的な例 認知システム論 探索( 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 ベストに見えるも のを優先的に展開 評価関数の決め方によって いろいろなバリエーションが ある 1.均一コスト探索 2.欲張り最良優先探索 3.A * 探索

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

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) 指数的 b d (b:分枝率,d: 解の深さ) 空間計算量 (space complexity) 指数的 b d 幅優先探索 と同じ

9 2. 欲張り最良優先探索 (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) = 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) b m ( m: 探索木の最大の深さ) 空間計算量 (space complexity) b m 深さ優先探索 と同じ

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

16 許容的ヒューリスティック (admissible heuristic) A P R S B 初期状態 ゴー ル 253 実際の最小コスト h*(n) = 278 予想最小コスト h(n) 直線距離 すべてのノード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 リストは常に,最適解の経路上にあるノードnを少な くとも1つ含み,非最適解のゴールノード G と次の関係を満 たす. f(n) = g(n) + h(n) ≦ g(n) + h*(n) = C* < f(G) よって,必ず, G より先に n が OPEN リストから選ばれ て展開される.したがって, G は決して OPEN リストから 選ばれない. 探索木

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

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

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

23 8パズルのヒューリスティック関数 54 618 7 3 2 12 8 3 4 765 ゴール 初期状態 候補1 h 1 = ゴールの位置にないタイルの数.上の例で は7. 候補2 h 2 = 各タイルのゴール状態までのマンハッタン 距離の和.上の例では18. 2+3+3 +3+3 +2+2 +4+4 +2+2 +0+0 +2+2 =18 ■ どちらも許容的(楽観的) ■ h 2 は h 1 より優位.

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

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

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

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

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

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

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

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


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

Similar presentations


Ads by Google