Lecture 5 田中 美栄子 ヒューリスティック探索 ヒューリスティック という概念を知る Heuristic:発見に役立つモノ(定義曖昧) 1957 Newell, Shaw, Simonの定義 「ある与えられた問題を解くかも知れないが、そ の可能性が保証されていないプロセス」(つまり 保証付きでない方策) 1961: 問題解決の動作効率を改良するヒン ト Herbert A. Simon “Science of Artificial” (人工物の科学→ 邦訳は 「システムの科学」) Heuristic:発見に役立つ知恵(定義曖昧) 1963 FeigenbaumとFeldmanによる定義: 「rule of thum のことである」 親指で1インチを測る程度の大雑把で、巨大な 探索空間を大幅に制限する為の戦略、仕掛け、 単純化、等の方法 解を保証しないが、多くの場合に良い解を提供する 後になってそれが,最適解だった,と判ることもある これまでは知識を用いない探索 (blind search)であった・・・ 対象とする事柄に対し 多少とも知識を持っている場合 ヒューリスティック・サーチが可能 ※(ヒューリスティック・サーチ:発見法的な探索) 探索の基本アルゴリズム Search algorithm{ 1. 初期節点をopenリストに入れる 2. LOOP:if(open==empty)break; (探索失敗) 3. n=first(open); 4. if(goal(n))print(n);break; (探索終了) 5. remove(n,open); 6. 次に調べる節点をopenに入れる(順序) 7. ステップ2にもどる} Heuristicの例(1) 各点に ゴールまでの推定コストを 仮定する ヒューリスティック探索(1) 最良優先探索:best-first search 各節点からゴールまでのコスト(距離)ℎ(𝑛)が 予想できるとき 全コストは 𝒇 𝒏 = 𝒈 𝒏 + 𝒉(𝒏) ℎ(𝑛)の正確な値が分からない時 予測値𝒉′(𝒏)で代用 ヒューリスティック探索(1) 最良優先探索:best-first search ステップ6で予測値𝒉′(𝒏)の昇順に並べる 次の例参照:出口までの x距離とy距離の和とす →駄目かもしれない 問題点 ヒューリスティック関数 ℎ′の 推定が間違っていれば失 敗 Heuristic:ヒントを多用して解を発見 例:迷路問題 ヒューリスティック関数 h’(n) = n→ G間の距離の推定値 h’(n)=|nx - Gx|+| ny 使えそうな知識 - Gy| これまでは知識を用いない探索 (blind search)であった、、 対象とする事柄に対し多少とも知識を持っている場 合、ヒューリスティック・サーチが可能 (Heuristic search:発見法的な探索) こういうときはこうするのがよい、という選択がで きる、但し100%信頼は出来ない(うまく行くことが 多い、または過去にうまく行ったことがある) h = 点nから目標地Gまでの推測コスト S(1,1)からG(4,4)へ h=|nのx座標-Gのx座標|+|nのy座標-Gのy座標| S(1,1)からG(4,4)へ A*-アルゴリズム A*-アルゴリズム A*-search algorithm{ 1. 初期節点をopenリストに入れる 2. LOOP:if(open==empty)break; (探索失敗) 3. n=first(open); 4. if(goal(n))print(n);break; (探索終了) 5. remove(n,open); 6. 次に調べる節点をopenに入れる(nを展開し、全 ての子節点𝑛𝑖 をopenに入れ、推定コスト𝑓(𝑛𝑖 ) の昇順に並べる)。さらに𝑛𝑖 から𝑛へポインタを 付ける。 A*-アルゴリズムとA-アルゴリズム 推定コスト A*の条件 𝒇 𝒏𝒊 = 𝒈′ 𝒏𝒊 + 𝒉′(𝒏𝒊 ) 推定値𝒉′ 𝒏𝒊 ≤ 本当の値𝒉(𝒏𝒊 ) この条件が成立しなければA-searchとなる。 A-searchならば解は保証されない 𝑔′(𝑛𝑖 )は𝑔(𝑛𝑖 )の推定値だが 出発点から𝑛𝑖 までの、解っているコストの内で最小のもの A*-アルゴリズム 探索例 S : 初期節点 G : 目標節点 A*-アルゴリズム 探索例 OPENリスト 1. S(6) A*-アルゴリズム 探索例 OPENリスト 1. S(6) 2.a(6) 3+3 A*-アルゴリズム 探索例 OPENリスト 1. S(6) 2. a(6) 3.b(6) , c(8) 3+1+2 3+1+4 A*-アルゴリズム 探索例 OPENリスト 1. S(6) 2. a(6) 3. b(6) , c(8) 4.e(6) , d(8) , c(8) 3+1+1+1 3+1+1+3 A*-アルゴリズム 探索例 OPENリスト 1. S(6) 2. a(6) 3. b(6) , c(8) 4.e(6) , d(8) , c(8) 5.G(6) , d(8) , c(8) 3+1+1+1 A*-アルゴリズム 探索例 OPENリスト 1. S(6) 2. a(6) 3. b(6) , c(8) 4.e(6) , d(8) , c(8) 5. G(6) , d(8) , c(8) 探索順番 S→a→b→e→G
© Copyright 2025 ExpyDoc