ヒューリスティック探索 （経験を用いた探索）
これまでに到達した探索木の末梢状態から展開される状態のうちこれまでに到達した探索木の末梢状態から展開される状態のうち，解に至る可能性の高い状態に注目し，探索の効率を高める．
末梢状態： 探索木上で，これまでに探索した端の状態．
末梢状態
探索木上で これまでに探索した端の状態
展開： 与えられた節点に対し，直接移行可能な全ての後継状態を作り出すこと．

探索の効率化に用いる判断基準
探索効率
用
判断 準 （（ヒューリスティック情報）
リィ ク情報）状態 ｓ における評価関数 （全コスト） ｆ（ｓ）
ｆ（ｓ） ＝ ｇ（ｓ） ＋ ｈ（ｓ）
ｇ（ｓ）： コスト関数
ｈ（ｓ）： ヒューリスティック関数
コストはゼロ以上：
ｇ（ｓ）≧（ ）≧ ０，０ｈ（ ）≧ ０ｈ（ｓ）≧
Computational Informatics 3, School of Informatics and Sciences, Nagoya Universityコスト関数 ｇ： 初期状態から現状態までのコストを与える．
同じ状態であっても，初期状態からの経路によりｇの値は異なる．
値は異なる
ヒューリスティック関数 ｈ：現状態から目的状態までの ストの予測値を与える
現状態から目的状態までのコストの予測値を与える．
同じ目標状態へのｈであっても経路により値は異なる．
全コストが小さくなるような問題解決を進める．
ヒューリスティック情報，複数の探索枝候補からの選択法→ 問題，解法固有．
問題，解法固有／ｓ1 h=7h 72 ／ ＼ 4h=6 ｓ2ｓ3
h=57 ／ ＼／ ＼ 4ｓg
ｓg’
g(s1)+9g(s1)+8
実際の スト
実際のコスト

各枝の数字が，その枝のコスト．
各枝の数字がその枝のコスト
ｓ1 までのコスト ｇ(s1)ｓ1 からどちらに行こうか？
f（s2）= g(s1) + 2 + 6= g(s1) + 8
f (s3) = g(s1) + 4 + 5= g(s1)( 1) + 9Computational Informatics 3, School of Informatics and Sciences, Nagoya Universityコスト関数とヒューリスティック関数に注目した効率化探索法
Ａアルゴリズム
ゴ ズ
初期状態も含めて，これまで展開された状態の評価関数値 ｆ（ｓ）が，より小さい状態を優先的に次の探索対象とする．
（ｇ を探索木の深さ，ｈ をゼロとすれば，横形探索）
Ａ＊ アルゴリズム
節点 のヒューリスティックス関数値 ｈ（ｓ） が，節点 ｓ から目標節点までの実際のコスト以下である，Ａアルゴリズム．
目標節点
実際
以あ ，リ
＊Ａ アルゴリズムでは最小のコストの枝を辿る．
／ｓ1
h = 7
ｓ1 までのコスト：g12 ／ ＼ 4
ｓ1 からどちらに行くか？
h = 6ｓ2ｓ3
h = 3
f (s2) = g1 + 2 + 6
7 ／ ＼ ／ ＼ 4
f (s3) = g1 + 4 + 3
ｓg
ｓg’ｓ3を選択
g1+9g19
g1+8
g1 8
実際のコストComputational Informatics 3, School of Informatics and Sciences, Nagoya University

最適解の探索

最小コストの解（最適解）が得られることを示す．

探索経路 （ｓｇ，（ｓｇｓｇ'：ｓｇ： 目標状態）
ｓ0 → ｓ1 → ｓ2 → ･･･ → ｓi ･･･ → ｓg
→ ｓj ･･･ → ｓg’

最適解
非最適解

最適解に至る状態列： ｓ0，ｓ1，ｓ2，･･･，ｓi，･･･，ｓg
最適解の全 スト最適解の全コスト：f b t （最適解の実際のコスト）．
f_best（最適解の実際の スト）
これは ｆ（ｓg） に等しい．
ｓi での全コストの見積もり： ｆ (ｓi) = g (ｓi) + h (ｓi)(ｓi)．
初期状態ならば f (ｓ0)．
ｓiでの実際の全コスト： ｆ＊(ｓi) = g(ｓi) + h＊(ｓi)．
これは最適のコスト f_best に等しい．
Ａ＊ の仮定より，の仮定より
h ((ｓi)i) ≦ h＊(ｓi)．
( i)
よって，ｆ (ｓi) ≦ ｆ＊(ｓi)．
つまり f (ｓi) ≦ ff_best．
つまり，fbest
Computational Informatics 3, School of Informatics and Sciences, Nagoya University今，最適でない経路で達する目標状態 ｓg’ があるとする．
すると，f_best ＜ ｆ (ｓg’)．
g
これより，f (ｓi) ≦ f_best ＜ ｆ (ｓg’)．
つまり，f (ｓi) ＜ ｆ (ｓg’)．
Ａアルゴリズムは，最小のズ
ｆ の状態を選ぶ．
→ ｓg’ より ｓi が選ばれるはず．
↓ｓg に到達する以前に ｓg’が選ばれることはない．
非最適解に至る途中の状態 ｓj に対して，f_best ＜ ｆ (ｓj)であるならば，最適解が見つかった時点では，ｓj は選ばれていない．
ばれな
Ａ＊ アルゴリズムは最適解を与える．
アルゴリズムは最適解を与える

Computational Informatics 3, School of Informatics and Sciences, Nagoya University

より情報を持つヒューリスティック関数 （ｈの良し悪し）
ｈ2 は ｈ1 より情報を持つ
iff
ｈ1（ｓ） ＜ ｈ2（ｓ） ≦ ｈ＊（ｓ）
より情報を持つヒューリスティック関数→ より少ない節点をたどって最適解にたどり着く．
より少ない節点をたどって最適解にたどり着く
ｈ1 を用いたＡ＊ アルゴリズム：
ｆ1 ＝ ｇ ＋ ｈ1
ｈ2 を用いたＡ＊ アルゴリズム：
ｆ2 ＝ ｇ ＋ ｈ2

(*1)

Ａ1＊
Ａ2＊

Computational Informatics 3, School of Informatics and Sciences, Nagoya University

(*1) を示すために，次のことを示す．
Ｓ1： Ａ1＊ により解を求めた時に展開される状態の集合，
Ｓ2： Ａ2＊ により解を求めた時に展開される状態の集合，において，においてＳ1 ⊇ Ｓ2(*2)

各Ａ＊ アルゴリズムで解が得られた時点を考える．
ｓ0 = ｓg の場合：

展開せずに解探索は終り．

ｓ00 ≠ ｓgの場合：の場合
１回目の展開： 評価対象となる次の状態が全て展開されるため Ａ1＊ でも Ａ2＊ でも，同じ数るため，Ａ1でも 同じ数の状態が作られる．
ここで解が得られたとしても，確かに (*2) が成立．
Computational Informatics 3, School of Informatics and Sciences, Nagoya University

探索が進み，Ａ1＊，Ａ2＊ ともに解に達したとしよう．
（背理法の仮定）Ａ1＊ が選択せず，Ａ2＊ が選択する状態， ｓi が存在する．
ｓii ∈ Ｓ1 でないが，でないがｓii ∈ Ｓ2 である．
である探索が終了した時，Ａ探索が終了した時
Ａ＊ アルゴリズムが最適解を与えることより，アルゴリズムが最適解を与えることより
ｆ1（ｓｇ） ＝ ｆ2（ｓｇ） ＝ f_bestとなっている．
一方，終了時点でＡ1＊ が選択しない節点 ｓi に対しては，
ｆ b t ＜ ｆ1（ｓi）
ｆ_bestｆ1（ i）
つまり，
ｆ best ＜ ｇ（ｓi）＋ｈ1（ｓi)ｆ_best(*3)

また，ｓi は Ａ2＊ で探索終了時には選択されているため，
ｆ2（ｓi） ≦ ｆ_best(*4)

Computational Informatics 3, School of Informatics and Sciences, Nagoya University

(*3)，(*4) より，ｇ（ｓｉ）＋ｈ2（ｓｉ）ｇ（）（） ＜ ｇ（ｇ（ｓｉ）＋ｈ1（ｓｉ））（）
ｈ2（ｓｉ）＜ ｈ1（ｓｉ）
れは，
これは，
ｈ2 は、ｈ1 より情報を持つこと，つまり，
（ ）
ｈ2（ｓ）
（ ） ≦ ｈ*（ｓ），（ ），ｈ1（ｓ）＜に反する．
よって背理法の仮定は誤り．
Ａ1＊ が展開せず， Ａ2＊ が展開する状態は存在しない．
Ａ2＊ が展開する状態の数は Ａ1＊ が展開する状態の数以下である．

Computational Informatics 3, School of Informatics and Sciences, Nagoya University

探索による問題解決の例
探索問題としての自然言語構文解析「大きい机がある。」を解析する．
が品詞
STATEMENT： 文 （最後の 。を含む）
S： 文本体 （ 。を含まない）
SUBJ (subject)： 主部
V (verb)： 動詞
N (noun)： 名詞
P (postposition)：
ADJ (adjective)： 形容詞
文法
STATEMENT ← S END
S ← SUBJ V
S ← V
SUBJ ← N P
SUBJ ← ADJ N P
辞書
END ← 。
N ← 椅子N ← 机P ← がV ← あるADJ ← 大きい大きADJ ← 小さい小さ助詞

Computational Informatics 3, School of Informatics and Sciences, Nagoya University

トップダウン法
１ｓｔ
STATEMENT／ ＼SEND

２ｎｄSTATEMENT／ ＼SEND／ ＼|SUBJV 。

３ｒｄ
STATEMENT／ ＼S
END
／ ＼|
SUBJ
V 。
／ ＼|N
P ある
こちらは失敗STATEMENT／ ＼S
END
／ ＼|
SUBJ
V 。
／ | ＼|ADJ N
P ある

STATEMENT
／ ＼S
END
||V。
こちらは失敗４ｔｈ
STATEMENT／＼S
END
／＼|
SUBJ
V。
／ | ＼|ADJNP
ある|||
大きい 机 がComputational Informatics 3, School of Informatics and Sciences, Nagoya Universityボトムアップ法
１ｓｔADJ|
大きいN
|机P
|がV
|あるEND|。

２ｎｄ（ADJ を伸ばす）
SUBJN
P
V／ | ＼|||
ADJ
N
P
机が ある
|
大きい３ｒｄ（N，P をつなげる，V を伸ばす）
SUBJ
SEND／ | ＼|
|
ADJ N
PV。
||||
大きい 机 があるEND|。

４ｔｈ
S を伸ばし STATEMENT を作り，END とつなげる．解析終了．とつなげる 解析終了
→ 失敗
S を伸ばしたことを取り消す．
を伸ばしたことを取り消す
V を伸ばしたことを取り消す．
（バックトラック）

Computational Informatics 3, School of Informatics and Sciences, Nagoya University

５ｔｈ（SUBJ を伸ばす）
S／ ＼SUBJ
V／ | ＼ADJ N
PV||||
大きい机 が あるEND|。

６ｔｈ（S を伸ばす．V をつなげる）
STATEMENT／ ＼S
END／ ＼SUBJV
END／ | ＼|
|
ADJ N
P ある。
|||
大きい 机 が７ｔｈ
END をつなげて完成をげ 完成

Computational Informatics 3, School of Informatics and Sciences, Nagoya University