第2回
発見的探索(1)
1
発展の歴史-1
1. 前史
•
•
チューリングテスト(1930年代) :A.Turing
チェスの理論研究(1940-50年代) :C.Shannon
2. 1950 - 60年代: 探索(知能)
•
•
•
ダートマス会議(1956): “AI”の誕生
Lisp(1958): LISt Program(J.MacCarthy)
楽観的予測: 「20年以内に計算機は人間と同等の
能力を持つ」(H.Simon, 1965)
2
探索の位置付け
弱い手法(weak method)の代表

与えられた問題の解決に関与する要因
の依存関係が複雑

未知の要因が含まれるため問題解決の
アルゴリズムを考案することが困難
→ 探索の一般的方法や中間結果の評価法
などの間接的な情報のみ与えて,コン
ピュータの処理能力に任せる
3
人間 vs コンピュータ
人間は全探索(しらみつぶし)はせず,
ヒューリスティクスを利用して
効率化を行っている
ヒューリスティクス:
常時ではないが多くの場合うまくいく経験則
4
探索の基本的な仮定


問題の解の候補は離散的
有効に数え上げが可能
vs ロボット径路策定問題(連続)
論理回路設計問題(組み合わせ的爆発)
解の候補が与えられたとき,真の解かど
うかを判定するアルゴリズムが存在
vs 機械翻訳・画像認識問題(評価基準未
知)
5
問題解決の定式化:解探索
状態空間中を初期状態から目標状態(解)に至る
径路を探索すること
・状態空間(state space):
状態を節点(node)、状態遷移を有向枝(arc)としたグラフ
で表現
・オペレータ:
状態遷移のための手段
~ 前提条件、削除リスト、追加リスト
・拘束条件:
目標達成のために守らねばならない条件
6
探索問題の例



迷路
積み木
8パズル
7
迷路探索の例
拘束条件:
左向き進行
禁止
8
積み木の例
相対的な位置関係を記述
9
8パズルの例
10
解探索の基本手法-1~知識は利用しない

縦型探索
深さ優先探索(depth-first search)
~ 深さ方向を優先的に展開
11
解探索の基本手法-2

横型探索
幅優先探索(breadth-first search)
~ 初期節点からの径路が浅い節点を
優先的に展開
12
解探索の基本手法(模式図)
親節点
子節点
13
基本手法の比較


縦型探索
- 停止しない危険性あり ←深さ方向に制限
- 最適解に到達する保証無し
- メモリ消費量は少ない
横型探索
- 径路長最短の解に到達する保証あり
- メモリ消費量は多い
14
解探索の基本手法改良-1

繰り返し縦型探索(反復深化)
~ 深さ限度を表す変数lにより縦型探索を制御
・同じノードを繰り返し生成するので,一見非効率
・既に評価が下っているため,
問題となるのはノード生成の時間のみ
15
解探索の基本手法改良-2

繰り返し横型探索
~ 幅の広さに制限を設け,少しずつ広げること
により,メモリ量の増大を抑制
16
計算量の比較
bl
bl
17
ヒューリスティクスを用いた状態空間探索
ヒューリスティクスを積極的にシステムに
取り込むことにより探索効率の向上を図
る
~ 独立モジュール化
代表例)
・Means End Analysis (MEA)
18
山登り法
現在吟味中の節点に対し、基本操作を施して到達でき
る次状態候補(現節点の子節点)の中で
最も評価値の高い節点を選択(局所的最適化)
ヒューリスティクス関数:山頂(目標)との高さの差
・縦型探索
・最適解の保証は無し
19
山登り法での局所的最小値
シミュレーテッド・アニーリング法:
探索範囲を探索時間経過と共に変化させる
20
最良優先探索(best-first search)
現局面(節点)から解に至るまでの予測評価
h(n)をヒューリスティクス関数として与え、
利用
・目標まで到達可能
・大容量メモリが必要
・最適解に到達する保証無し
21
ビーム探索(beam search)
最良優先探索で評価値の高いほうからN個、
またはしきい値以上のもののみ残すことにより、
メモリの増大を抑制
・最適解に到達する保証無し
例)CMU・音声理解システムHappy (1970年代)
22
反復深化(iterative deeping)
深さ優先(縦型)探索で,探索の深さ制限を,
最初は1個、
ゴールが見つからなければ
段階的に1つずつ増大
・使用メモリ量 小 (縦型探索と同様)
・最も浅い位置のゴールを最初に発見可能
(横型探索と同様)
・探索負担は増大
23
Means End Analysis (MEA)
以下の処理を反復

現在の状態を目標状態と比較

差異を減少させる操作を選択

可能ならその操作を適用.可能でなけれ
ば現在の状態を退避,部分問題に適用

部分問題が解決されたら退避した問題を
回復,解探索作業を再開
24
MEAにおけるヒューリスティクス知識
以下の関数として実現

2つの状態の間の差異を計算する関数

与えられた差異の解消に貢献する操作
を選択する関数

解として許される操作の系列に関する
制約
25
解探索の効率化
問題固有の知識利用
- 枝のコスト: 2地点間の距離、経費、・・
- 節点評価値: 目標節点への近さ
~ ヒューリスティクス関数
- 合併評価

探索手続きの改良
- 山登り法 (hill-climbing method)
- 分枝限定法 (branch-and bound method)

26
コスト関数
初期状態S0, O1(So)=S1, O2(S1)= S2, ・・
となる操作系列{Oi}:
f(p) =
C(Oi)
i
が最小となる系列を求める
27
分枝限定法
山登り法の改良 ~
現節点の子節点に限定せず、これまでに
展開されながら利用されていない節点の
うち最適なものを選択
・オペレーションズリサーチ(OR)における
組合せ最適化問題にて提案
・横型探索の改良型
28
組合せ最適化問題(OR)
離散領域D:
制約条件を満足する実行可能解の集合
において,
目的関数:f(x)→最小(または最大)
制約条件:x∈D
となる最適解xを求める問題
[方策] 最適解となる可能性の無い部分領
域の探索を刈る(pruning)
29
分枝限定法における探索
これまでに展開した節点のうち,
初期節点から現節点に至る経路コストが
最小である節点を選択し,
この点から子節点を展開し,
それらを展開済かつ未探索の節点群に加え,
そのうちで経路コスト最小のものを選ぶ
ことを反復
30
分枝限定法による探索の例
S – [C(1), B(2)] – [B(2), F(4), H(5)] –
[D(3), E(4), F(4), H(5)] – [E(4), F(4), H(5), G1(5), I(6)]
31
状態評価関数
f(n) = g(n) + h(n)
h(n) ≧0
h(n): 現局面(節点n)から解に至るまでの予測評価(最小コスト)
g(n): 初期状態S0から現局面までの評価(最小コスト)
h(n)は未知→ ヒューリスティクス関数の導入
f(n) = g(n) + h’(n)
∀n: h’(n) ≦h(n);楽観的(許容的)ヒューリスティクス関数
ex) h’(n) =0: 横型探索アルゴリズムと等価
~ 最適解への到達保証,状態空間削減不可
代表例) A*アルゴリズム
32
A*アルゴリズム
Aアルゴリズム:
最良優先探索の改良 ~
現局面(節点)から解に至るまでの予測評価h(n)に出発
点から現局面までの評価g(n)を加味
f(n) = g(n) + h(n)
→ f(n) = g(n) + h’(n)
h’(n) ≦h(n) ;楽観的なヒューリスティクス関数
最適解への到達を保証
~AIにおける代表的な探索方式 (分枝限定法の一種)
33
A*アルゴリズムの例:8-パズル
h’(n): ゴール状態と異なる位置におかれたタイル数
h’(n) ≦h(n): ゴールまでに動かさないといけないタイル数
が保証される
34
ダウンロード

研究テーマ: 状況・状態把握技術