知識に基づく探索

認知システム論探索（3）
先を読んで知的な行動を選択するエージェント
知識に基づく探索
─ ヒューリスティック探索 ─
(Heuristic Search)
最良優先探索
均一コスト探索
欲張り最良優先探索
Ａ* 探索
最良優先探索の
具体的な例
ヒューリスティック関数について
復習：一般的探索アルゴリズム
展開する＝子を産む
未展開ノードはオープンリストに並
べる
子から親への
ポインタ
必ず先頭から取り除き
展開する
F
子
S
A
A
オープンリスト
T
O
Z
R
戦略に基づいて
適切な位置に挿入
B
経路コストの導入
初期状態
71 O
75 Z
経路コスト
N
151
140
A
118
F
R
70
P
146
M
75
D
ゴール
97
L
120
V
211
最適解
111
I
92
99
S
80
T
87
85 U 98
B
101
138
C
142
90
G
H
86
E
最良優先探索(best-first search)
オープンリスト
A
5
T
7
Z
10
R
16
評価関数 (evaluation function)
f(n) の小さい順になるよう挿入
評価値＞0
ベストに見えるものを
優先的に展開
O
15
B
8
評価関数の決め方によって
いろいろなバリエーションがあ
る
１．均一コスト探索
２．欲張り最良優先探索
３．Ａ* 探索
１．均一コスト探索(uniform cost search)
初期状態からそのノードn までの経路コスト g(n)
を評価関数とする最良優先探索
初期状態
a
0
5
ゴールに向かって
のシャープな探索に
なっていない
現在状態
b
5
3
n
8
g(n) = 5+3 = 8
全オペレータのコスト＝１なら，幅優先探索と同じ動作となる
均一コスト探索の実行
オペレー
タのコスト
0
経路コスト g(n) の低い順に展開
4
1
経路コス
ト
1+2=3
9
12
1
2
3
2
5
4
1
7
9
オープンリスト
2
2
7
3
6
7
9
IN
OUT
8
経路コスト g(n) の
昇順になるように
挿入
均一コスト探索の最適性
ただし，オペレータのコストは非負とする
S
A
start
S
1
10
5
B
15
5
5
C
goal
G
1
A
G
1
10
11
B
0
15
C
5
G
5
15
5
10
展開のために選択
してゴールと判定
展開のために選択したと
きにゴールと判定する
均一コスト探索の性質
完全性(completeness) あり
解があれば必ず見つける
最適性(optimality) あり
最適解を最初に見つける
時間計算量(time complexity)
指数的ｂd （ｂ：分枝率，ｄ：解の深さ）
空間計算量(space complexity)
指数的ｂd
幅優先探索
と同じ
２．欲張り最良優先探索
(greedy best-first search)
そのノードn からゴールまでの予想コスト h(n)
を評価関数とする最良優先探索
初期状態
a
0
5
現在状態
b
5
3
ヒューリスティック関数
ノードからゴールまでの
最短経路コストの見積り
これの小さい順に展開
n
8
h(n)
ゴール
g
ヒューリスティック(heuristic)とは？
語源：アルキメデスが風呂で浮力の法則を
発見したときに叫んだ”Heurika !” （ユーリカ！
発見した！）
経験から発見した知識のこと
最悪ケースの性能は必ずしも上げないが，平
均的または典型的にはうまくいく手法
ヒューリスティック関数の例：直線距離
初期状態
Z
A
T
374
h(n) = ｎからゴールまでの直線距離
S
329
253
ゴール
B
欲張り最良優先探索は最適性がない
h の値（直線距離）
Z
欲張ってこっちにこだわった
374
253
A
S
366
T
329
（欲張り最良優先探索）
99
F
178
しかし多くの場合
うまくいく
80
193
R
最短経路はこちら！
（最適性がない）
97
211
P
101
B
0
欲張り最良優先探索は完全性がない
Z
374
A
366
T
150
T1
150
T2
150
253
S
不適切なヒューリスティクス
B
0
欲張り最良優先探索の性質
完全性(completeness) なし
解を見つけないことがある
最適性(optimality) なし
最適解を見つける保証がない
時間計算量(time complexity)
ｂｍ（ｍ：
探索木の最大の深さ）
空間計算量(space complexity)
ｂｍ
深さ優先探索
と同じ
エイスター
３．A* 探索(A* search)
経路全体の予想コスト f(n)=g(n)+h(n)
をコスト関数とする最良優先探索
初期状態
n
5
3
現在状態
8
g(n) h(n)
ここまでのコスト
ゴール
ここからの予想コスト
ｆ(n) = g(n) + h(n)
n を経由する最短経路の見積もりコスト
これの小さい順に展開
許容的ヒューリスティック(admissible heuristic)
予想最小コスト h(n) ≦ 実際の最小コスト h*(n)
を満たすヒューリスティック関数のこと
初期状
態
A
楽観的(optimistic)
ヒューリスティック
とも言う
予想最小コスト h(n)
S
253
直線距離
ゴール
R
実際の最小コスト h*(n)＝278 P
B
A* 探索の性質
完全性(completeness) あり！
解があれば必ず見つける
最適性(optimality)
許容的ヒューリスティクスの場合，あり！
最初に見つけた解は最適解
時間計算量(time complexity)
空間計算量(space complexity)
ヒューリスティックの
精度に依存
許容的ヒューリスティクスにより
A*が最初に見つける解は最適解
経路コスト
O
Z 71
75 449 374
A
366
366 140
118
T
447 329
526 380
151
S
h 関数の値
（直線距離）
393 253 F
99 417178
80
R 413 193
211
97 P
B
415 98
B 450
146
101 418
0
C 526 138
160 C
615
最適解
160
A*探索の振る舞い（１）単調性
526
449
366
探索木に沿ったすべての経路で
f のコストは非減少
393
447
417
413
415
526
615
450
418
 しかし，すべての問題が単調性が成り立つわけではない．
A*探索の振る舞い（２）単調性の定義
単調性
h(n)  h(n ')  c(n, n ')
三角不等式に
似ている
 先へ進んで，情報が得られてくるほど，楽観性が弱くなる
h(n ')  h(n)  c(n, n ')
n
h(n)
c(n,n')
ゴール
n'
h(n')
A*探索の振る舞い（３）等高線
449
f = 366
の等高線
366
A*アルゴリズムは f 値の山を
ゴールに向かって，見落としなく
（シャープに）単調に登っていく
526
393
413
415
393
447
418
417
413
最適解の等高線
準最適解
415
最適性あり！
完全性あり！
417
526
615
 実際には，単調性がなくても，最適性と完全性がある．
450
418
ただし，許容的
ヒューリスティック
最良優先探索の比較
均一コスト
欲張り
Ａ*
完全
○
×
○
最適
○
×
○
時間
×
△
△
空間
×
△
△
幅優先的
深さ優先的
ヒューリスティクス
次第
 つねに h(n)=0 とすれば，A*は均一コスト探索と一致する．
ヒューリスティック関数について
ヒューリスティックの優位性
８パズルのヒューリスティック
ヒューリスティック関数の作り方
ヒューリスティックの優位性
≦ h2(n) ≦ h*(n)
h2 は h1 より優位
h1 で展開されたノード
⊆
すべてのノード n において h1(n)
実際の
値
h2 で展開されたノード
８パズルのヒューリスティック関数
初期状態
候補１
1
5
4
6
1
8
8
7
3
2
7
2
3
ゴール
4
6
5
h1=ゴールの位置にないタイルの数．上の例では７．
候補２ h2=各タイルのゴール状態までのマンハッタン距離
の和．上の例では１８．
２＋３＋３＋２＋４＋２＋０＋２＝１８
■どちらも許容的（楽観的）
■h2はh1より優位．
８パズルの実験結果
解の長さ
展開した平均ノード数
反復深化
A*(h1)
A*(h2)
2
10
6
6
4
112
13
12
6
680
20
18
8
6384
39
25
10
47127
93
39
12
364404
227
73
14
3473941
539
113
16
1301
211
18
3056
363
20
7276
676
22
18094
1219
24
39135
1641
ヒューリスティック関数の作り方（１）
緩和問題
＝オペレータに対する制限を減らして
解きやすくした問題
(relaxed problem)
８パズルの場合：
となりにタイルが置いて
あってもそこに動かせる
 緩和問題の正確な解のコストが元の問題の
良いヒューリスティクスになっていることが多い
ヒューリスティック関数の作り方（２）
緩和問題の自動生成
AがBのとなり＆
Bが空
relax
AがBのとなり
（無条件で）
→
AからBへタイル
を動かせる
h2
h1
→
AからBへタイル
を動かせる
→
AからBへタイル
を動かせる
ヒューリスティック関数の作り方（３）
h1,h2,…,hm という許容的ヒューリスティクスがあり，
どれも他の優位にないとき，どれを選ぶか？
h(n) = max (h1(n), h2(n), …, hm(n) )
■ ｈは一つひとつの関数より優位
ヒューリスティック関数の作り方（４）
統計情報の利用
h2(n)=14
→
90%の確率で実際のコスト＝18
許容性の保証はなくなるが
平均的に効率が向上する
h(n)=18
ヒューリスティック関数の作り方（５）
状態の「特徴」の利用
将棋の例
h(n)=α×駒の得点の差
＋β×駒の働きの差
＋γ×玉の囲いの差
α β γ：学習アルゴリズムで値を調整する

Download Report