algorithm(知識を用いるヒューリスティック探索、AアルゴリズムとA

Report
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

similar documents