第２回　 発見的探索（１）

発展の歴史-1 前史 2. 1950 - 60年代: 探索（知能） チューリングテスト(1930年代) ：A.Turing チェスの理論研究(1940-50年代) ：C.Shannon 2. 1950 - 60年代: 探索（知能） ダートマス会議(1956): “ＡＩ”の誕生 Lisp(1958): LISt Program(J.MacCarthy) 楽観的予測：　「２０年以内に計算機は人間と同等の能力を持つ」（H.Simon, 1965)

探索の位置付け 弱い手法(weak method)の代表 与えられた問題の解決に関与する要因の依存関係が複雑 未知の要因が含まれるため問題解決のアルゴリズムを考案することが困難 →　探索の一般的方法や中間結果の評価法などの間接的な情報のみ与えて，コンピュータの処理能力に任せる

人間 ｖｓ コンピュータ 人間は全探索（しらみつぶし）はせず， ヒューリスティクスを利用して 効率化を行っている ヒューリスティクス： 人間　ｖｓ　コンピュータ 人間は全探索（しらみつぶし）はせず， ヒューリスティクスを利用して 効率化を行っている ヒューリスティクス： 常時ではないが多くの場合うまくいく経験則

探索の基本的な仮定 問題の解の候補は離散的 有効に数え上げが可能 ｖｓ ロボット径路策定問題（連続） 論理回路設計問題（組み合わせ的爆発） 問題の解の候補は離散的 有効に数え上げが可能 ｖｓ　ロボット径路策定問題（連続） 　　　論理回路設計問題（組み合わせ的爆発） 解の候補が与えられたとき，真の解かどうかを判定するアルゴリズムが存在 ｖｓ　機械翻訳・画像認識問題（評価基準未知）

問題解決の定式化：解探索 状態空間中を初期状態から目標状態（解）に至る径路を探索すること ・状態空間（state space)： 　状態を節点(node)、状態遷移を有向枝（arc)としたグラフで表現 ・オペレータ： 　状態遷移のための手段　 ～　前提条件、削除リスト、追加リスト ・拘束条件： 　目標達成のために守らねばならない条件　

探索問題の例 迷路 積み木 ８パズル

迷路探索の例 拘束条件： 左向き進行 　禁止

積み木の例 相対的な位置関係を記述

８パズルの例

解探索の基本手法-1～知識は利用しない 縦型探索 深さ優先探索(depth-first search) 　～　深さ方向を優先的に展開

解探索の基本手法-2 横型探索 幅優先探索(breadth-first search) 　～　初期節点からの径路が浅い節点を 　　優先的に展開

解探索の基本手法（模式図） 親節点 子節点

基本手法の比較 縦型探索 - 停止しない危険性あり ←深さ方向に制限 - 最適解に到達する保証無し - メモリ消費量は少ない 横型探索 縦型探索 - 停止しない危険性あり　←深さ方向に制限 - 最適解に到達する保証無し - メモリ消費量は少ない 横型探索 - 径路長最短の解に到達する保証あり - メモリ消費量は多い

解探索の基本手法改良-1 繰り返し縦型探索（反復深化） ～ 深さ限度を表す変数lにより縦型探索を制御 ・同じノードを繰り返し生成するので，一見非効率 ・既に評価が下っているため， 問題となるのはノード生成の時間のみ

解探索の基本手法改良-2 繰り返し横型探索 　～　幅の広さに制限を設け，少しずつ広げることにより，メモリ量の増大を抑制

計算量の比較 bl bl

ヒューリスティクスを用いた状態空間探索 ヒューリスティクスを積極的にシステムに 取り込むことにより探索効率の向上を図る 　～　独立モジュール化 代表例） 　・Means End Analysis (MEA)

山登り法 現在吟味中の節点に対し、基本操作を施して到達できる次状態候補（現節点の子節点）の中で 最も評価値の高い節点を選択（局所的最適化） ヒューリスティクス関数：山頂（目標）との高さの差　 ・縦型探索 ・最適解の保証は無し

山登り法での局所的最小値 シミュレーテッド・アニーリング法：　 探索範囲を探索時間経過と共に変化させる

最良優先探索(best-first search) 現局面（節点）から解に至るまでの予測評価h(n)をヒューリスティクス関数として与え、利用 ・目標まで到達可能 ・大容量メモリが必要 ・最適解に到達する保証無し

ビーム探索(beam search) 最良優先探索で評価値の高いほうからＮ個、 ・最適解に到達する保証無し またはしきい値以上のもののみ残すことにより、 メモリの増大を抑制 ・最適解に到達する保証無し 例）CMU・音声理解システムHappy　(1970年代)

反復深化(iterative deeping) 深さ優先（縦型）探索で，探索の深さ制限を， 最初は１個、 ゴールが見つからなければ 段階的に１つずつ増大 ・使用メモリ量　小　（縦型探索と同様） ・最も浅い位置のゴールを最初に発見可能 （横型探索と同様） ・探索負担は増大

Means End Analysis (MEA) 以下の処理を反復 現在の状態を目標状態と比較 差異を減少させる操作を選択 可能ならその操作を適用．可能でなければ現在の状態を退避，部分問題に適用 部分問題が解決されたら退避した問題を回復，解探索作業を再開

MEAにおけるヒューリスティクス知識 以下の関数として実現 ２つの状態の間の差異を計算する関数 与えられた差異の解消に貢献する操作を選択する関数 解として許される操作の系列に関する 制約

解探索の効率化 問題固有の知識利用 - 枝のコスト： ２地点間の距離、経費、・・ 問題固有の知識利用　 - 枝のコスト：　２地点間の距離、経費、・・ 　- 節点評価値：　目標節点への近さ 　 ～　ヒューリスティクス関数 　- 合併評価 探索手続きの改良 　- 山登り法　(hill-climbing method) 　- 分枝限定法 (branch-and bound method)

コスト関数 初期状態S0, O1(So)=S1, O2(S1)= S2, ・・ となる操作系列｛Ｏｉ｝： f(p) = 　となる操作系列｛Ｏｉ｝： f(p) = が最小となる系列を求める

分枝限定法 山登り法の改良 ～ 現節点の子節点に限定せず、これまでに展開されながら利用されていない節点の うち最適なものを選択 山登り法の改良　～ 　現節点の子節点に限定せず、これまでに展開されながら利用されていない節点の うち最適なものを選択 ・オペレーションズリサーチ(OR)における 　組合せ最適化問題にて提案 ・横型探索の改良型

組合せ最適化問題（OR) 離散領域D： 制約条件を満足する実行可能解の集合 において， 目的関数：f(x)→最小（または最大） 制約条件：x∈D となる最適解ｘを求める問題 [方策]　最適解となる可能性の無い部分領域の探索を刈る(pruning)

分枝限定法における探索 これまでに展開した節点のうち， 初期節点から現節点に至る経路コストが 最小である節点を選択し， この点から子節点を展開し， それらを展開済かつ未探索の節点群に加え， そのうちで経路コスト最小のものを選ぶ ことを反復

分枝限定法による探索の例 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)]

状態評価関数 f(n) = g(n) + h’(n) 代表例） Ａ＊アルゴリズム 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: 横型探索アルゴリズムと等価 ～　最適解への到達保証，状態空間削減不可 代表例）　Ａ＊アルゴリズム

Ａ＊アルゴリズム Ａアルゴリズム: 最良優先探索の改良　～ 現局面（節点）から解に至るまでの予測評価h(n)に出発点から現局面までの評価g(n)を加味 　 f(n) = g(n) + h(n) →　f(n) = g(n) + h’(n) 　h’(n) ≦h(n) ；楽観的なヒューリスティクス関数 最適解への到達を保証 　　～ＡＩにおける代表的な探索方式　（分枝限定法の一種）

Ａ＊アルゴリズムの例：８-パズル h’(n)： ゴール状態と異なる位置におかれたタイル数 h’(n) ≦h(n)：　ゴールまでに動かさないといけないタイル数 　が保証される