人工知能2 2005Apr26,May10

08人工知能4:知識を用いる探索法
(ヒューリスティック探索)
2008 May2
田中美栄子(知識A)
ヒューリスティック
という概念を知る
これまでは知識を用いない探索
(blind search)であった、、
• 対象とする事柄に対し多少とも知識を持っている場
合、ヒューリスティック・サーチが可能
(Heuristic search:発見法的な探索)
• こういうときはこうするのがよい、という選択ができる、
但し100%信頼は出来ない
• (うまく行くことが多い、または過去にうまく行ったこ
とがある)
Heuristic:発見に役立つモノ(定義曖昧)
• 1957 Newell, Shaw, Simonの定義
「ある与えられた問題を解くかも知れないが、そ
の可能性が保証されていないプロセス」
(つまり保証付きでない方策、といっている)
• 1961: 問題解決の動作効率を改良するヒント
Heuristic:発見に役立つ知恵(定義曖昧)
1963 FeigenbaumとFeldmanによる定義:
「rule of thum のことである」
親指で1インチを測る程度の大雑把で、巨大な探
索空間を大幅に制限する為の戦略、仕掛け、単
純化、等の方法
解を保証しないが、多くの場合に良い解を提供する
後になってそれが,最適解だった,と判ることもある
ロボットの迷路抜け
• (1,1)から(4,4)へ
(2,4)
(1,4)
(2,3)
(3,4)
(1,1)
(4,4)
(2,3)
(2,4)
(3,3)
(2,2)
2
(3,2)
(1,4)
(2,2)
(3,4)
(3,2)
(3,1)
4
(4,4)
(1,1)
(3,1)
(3,3)
知識を用いない探索(blind search)
• 解がどのあたりにあるかの見当がつかない場合、
総当たり的に探す(Brute-force search)
• 深さ優先探索(Depth-first-search)
• 幅優先探索(Breadth-first-search)
• 最適探索(Optimal-search)複数解のうち,最適解
Depth-1ST 深さ優先探索(graph)
depth-first-search algorithm{
1.初期節点をopenリストに入れる
2. if(open==empty)break;(探索失敗)
3. n=first(open);
4. if(goal(n))print(n);break;(探索終了)
5. remove(n,open); add(n,closed);
6. 次に調べる節点をopenに入れる(nを展開し、
全ての子節点niをopenの先頭に入れる)。
niからnへポインタを付けておく。
7. 2へもどる}
Depth-1st:S→A→B→D→E→G
• OpenList
1)
2)
3)
4)
5)
6)
S
A
BC
DEC
EC
GFC
S(1,1)
A(2,3)
B(2,4)
C(2,2)
2
H(3,2)
D(1,4)
E(3,4)
I(3,1)
4
G(4,4)
F(3,3)
Breadth-1ST 幅優先探索(graph)
breadth-first-search algorithm {
1.初期節点をopenリストに入れる
2. if (open == empty) break; (探索失敗)
3. n = first (open);
4. if (goal(n)) print(n); break; (探索終了)
5. Remove (n, open); add (n, closed);
6. 次に調べる節点をopenに入れる(nを展開し全ての
子節点niをopenの最後に入れる)。
niからnへポインタを付けておく。
7. 2へもどる
}
Breadth-1st:S→A→B→C→D→E→H →I→ G
• OpenList
1) S
2) A
3) BC
4) CDE
5) DEHI
6) EHI
7) HIGF
8) IGF
9) GF
S(1,1)
A(2,3)
B(2,4)
C(2,2)
2
H(3,2)
D(1,4)
E(3,4)
I(3,1)
4
G(4,4)
F(3,3)
Optimal-search
最適探索
optimal-search algorithm
{
1.初期節点をopenリストに入れる
2. if (open == empty) break; (探索失敗)
3. n = first(open);
4. if (goal(n)) print(n); break; (探索終了)
5. remove(n,open); add(n,closed);
6. 次に調べる節点をopenに入れる(nを展開し、全て
の子節点niをopenに入れ、コストの昇順に並べる)
niからnへポインタを付けておく
7. 2へもどる
}
最適探索optimal search
• 状態空間がグラフで表され
• 状態遷移の枝に出発点からのコスト g(n)
が計算済み
• この時、ステップ6でopenの中身をコストの昇
順に並べ、一番最初にコスト最小の節が来る
ようにする
• 解が複数ある場合など、最小コストの解を探
せる
Optimal:S→B→E→A→F→G2
• OpenList
S
1
4
B
A
1
1)
2)
3)
4)
5)
6)
2
S(0)
E
C
B(1)A(4)
D
4
E(3)A(4)F(4)
H
A(4)F(4)G1(6)H(7)
F(4)C(5)G1(6)H(7)
G2(5)C(5)G1(6)D(6)I(6)H(7)
2
3
F
2
1
3
G1
I
G2
これまでは知識を用いない探索
(blind search)であった、、
• 対象とする事柄に対し多少とも知識を持って
いる場合、ヒューリスティック・サーチが可能
(Heuristic search:発見法的な探索)
• こういうときはこうするのがよい、という選択
ができる、但し100%信頼は出来ない(うまく
行くことが多い、または過去にうまく行ったこ
とがある)
探索の基本アルゴリズム
•
•
•
•
•
•
•
•
Search algorithm{
1.初期節点をopenリストに入れる
2. if(open==empty)break;(探索失敗)
3. n=first(open);
4. if(goal(n))print(n);break;(探索終了)
5. remove(n,open);
6. 次に調べる節点をopenに入れる(順序)
7. 2へもどる}
Heuristic search(1)
最良優先探索:best-first-search
各節点からゴールまでのコスト(距離)h(n)が予想出来るとき
全コストは f(n)=g(n)+h(n)
h(n)の正確な値がわからないとき、予測値h’(n)で代用
• ステップ6で予想値h’(n)の昇順に並べる
(次の例参照:出口までのx距離とy距離の和とする:
→ 駄目かも知れない)
問題点
ヒューリスティック関数 h’ の
推定が間違っていれば失敗
Heuristic:ヒントを多用して解を発見
例:迷路問題
ヒューリスティック関数 h’:
h’(n)=状態nから終点Gまでの距離の推定値,と仮定
h’(n)=|nx ー Gx|+|ny ー Gy|
迷路の形次第で成功することも失敗することもある
ゼッタイに正しいかどうか解らないが使えそうなヒント
h = 点nから目標地Gまでの推測コスト
• S(1,1)からG(4,4)へ
(2,4)
(1,4)
(2,3)
(3,4)
S(1,1)
(4,4)
A(2,3)
B(2,4)
(3,3)
C(2,2)
2
D(1,4)
(2,2)
E(3,4)
H(3,2)
(3,2)
I(3,1)
4
G(4,4)
(1,1)
(3,1)
F(3,3)
h =|nのx座標-Gのx座標|+| nのy座標-Gのy座標|
• S(1,1)からG(4,4)へ
(2,4)
(1,4)
(2,3)
(3,4)
(3,3)
S(1,1)6
(4,4)
A(2,3)3
B(2,4)2
C(2,2)4
2
H(3,2)
D(1,4)3
(2,2)
E(3,4)1
(3,2)
I(3,1)
4
G(4,4)0
(1,1)
(3,1)
F(3,3)
A*-アルゴリズム
A*-search algorithm{
1.初期節点をopenリストに入れる
2. if(open==empty)break;(探索失敗)
3. n=first(open);
4. if(goal(n))print(n);break;(探索終了)
5. remove(n,open); add(n,closed);
6. 次に調べる節点をopenに入れる(nを展開し、全ての
子節点niをopenに入れ、推定コストf(ni)の昇順に並べ
る)
niからnへポインタを付けておく
7. 2へもどる}
A*-アルゴリズムとA-アルゴリズム
推定コスト
f(ni)=g’(ni)+h’(ni)
A*の条件
推定値h’(ni) <= 本当の値h(ni)
(この条件が成立しなければ A-search となる.
A-Search ならば 解は保証されない )
g’(ni)はg(ni)の推定値だが、出発点からniまで
の、解っているコストの内で最小のもの。
A*-algorithm:S→A→B→E→G
• OpenList
S(1,1)6
3
1)
2)
3)
4)
5)
S(6)
A(6)
B(6)C(8)
E(6)D(8)C (8)
G(0)D(8)C(8)
A(2,3)3
1
1
B(2,4)2
C(2,2)4
2
H(3,2)
D(1,4)3
E(3,4)1
I(3,1)
4
G(4,4)0
F(3,3)
h = 点nから目標地Gまでの推測コスト
• S(1,1)からG(4,4)へ
(2,4)
(3,4)
S(1,1)
(4,4)
A(2,3)
B(2,4)
(3,3)
(1,3)
C(2,2)
(2,3)
2
D(1,4)
(2,2)
E(3,4)
H(3,2)
(3,2)
I(3,1)
4
G(4,4)
(1,1)
(3,1)
F(3,3)