改訂新版 世界大百科事典 「探索理論」の意味・わかりやすい解説
探索理論 (たんさくりろん)
search theory
問題を解決するために用いる手段がいくつもある場合，そのいずれかを選択しながら解を得ていくための手順や方法に関する理論をいう。とくに人工知能で扱う問題は，その解法が決まらないことが多いので，探索によって答えを求めなければならない。
探索の典型的な例は，図に示す迷路の問題である。出発点Sから目標点Gまでの道を見つけるためには，分岐点でどちらへ行くかを選択しなければならない。図の分岐点と端点に名前がつけられているが，これを節点と呼ぶ。分岐点でどちらの道をとるかをでたらめに選ぶと，ループに入ってしまって目標に達しないことがある。それを避けるため，系統的な探索法が必要である。系統的探索法には，深さ優先探索と幅優先探索がある。深さ優先探索は，最初に一つの道を最後まで調べる。図の例で，分岐点では必ず右の道を選択すれば，最初にCへ行く。これが端点であるので次にSまで後戻りしてBへ行く。そして，E，Hの順に調べ，それが失敗するとEまで後戻りして，次にFを調べる。このようにすれば必ずGに達する。幅優先探索は，先へ進む前に広く探索する。図の例では，まずA，B，Cを調べ，次にその先のD，Eを調べる。この方法でも必ずGに達することができる。
もし，問題に関して何らかの知識を持っていれば，効率的に探索を行うことができる。たとえば図の例で，Gが右上にあることがわかっていれば，分岐点では右か上へ行く道を先に調べることができる。この方法は，上へ向かって山に登る方法と似ているので，山登り法と呼ばれる。さらに，各節点から目標までの道の長さ（探索のコスト）が予測できれば，その最小の節点から先を調べれば探索のコストを最小にすることができる。この探索法を最良優先探索と呼ぶ。問題によっては，道を見つけるだけでなく，コスト（たとえば長さ）が最小の道（最適解）を見つけなければならない。もし二つの節点を直接結んでいる道のコストが一定であれば，幅優先探索によって最適解が見つけられる。道によってコストが変わる場合に対しては，幅優先探索を改良した分岐限定法branch and bound methodが使える。もし各節点から目標までのコストが予測できる場合には，さらに効率のよい探索法がある。一般の問題も，使うことのできる手段を節点で選択できる道に対応させ，その手段を使った結果の状態を道によって結ばれている節点に対応させれば，迷路の問題に帰着することができる。
もう一つ別の探索として，ゲームのための探索がある。チェスや将棋のような2人ゲームでは，各局面で2人が交互に手段を選ぶことができる。各局面を節点に対応させれば迷路と似た問題になるが，相手がいることが異なる。つまり，相手が手段を選ぶ場合には，相手にとってなるべく有利な選択を行う。ゲームの戦略としては，ミニマックス法がよく知られている。ミニマックス法より探索の手間が少なくてすむアルファ-ベータ（α-β）法がゲームのための探索の基本となっている。目標までのコストが予測できる場合の探索法を応用した，さらに効率のよい探索法も研究されている。
探索を高速に行えば，多くの可能性を調べることができる。チェスの探索を高速に実行するためのチェスマシンも作られている。探索のプログラムを書くのに便利なプログラム言語も研究されている。たとえばPROLOG（プロローグ）は，問題をプログラムで表せば自動的に探索を行ってくれる。また，与えられた拘束条件を満たす探索をすることは，スケジュール作成などに応用でき，そのための言語も開発されている。問題を解決するには，探索だけでなく，探索の範囲を限定する知識も大切である。人間のように，多くの知識を使い，少ない探索で解を求めることも重要な研究課題である。
執筆者：白井 良明
探索理論の実際
オペレーションズリサーチにおいて探索理論とは，所在が明らかでない目標を見つけるための効果的な方法・手順に関する理論をいい，捜索理論ともいう。なお，対象となる目標物は，遭難者が乗ったゴムボートや潜水艦のように，電磁波，音波など物理的な信号によって探知できるものに限定される。探索理論は，第2次大戦中にアメリカ海軍のオペレーションズリサーチ・グループによって開拓された。対潜水艦戦の必要に応えるためである。その後，理論は発展し，列国の海軍にとって必須の研究課題となった。また応用分野もひろがり，最近は油田の探索のような場面にも応用されているが，洋上の遭難船の捜索・救難活動に対する適用が最もよく知られた実用例であり，ここではそれを例に説明する。アメリカの沿岸警備隊は，探索理論に基づくCASPと呼ばれる情報処理システムを利用して毎日の捜索・救難作戦を展開している。
探索理論の内容は探知論と探索計画の最適化理論とに大別される。探知論は，目，レーダーあるいはソナーなど，探索に用いられるセンサーの特性・能力に関する知識体系である。ソナーを例にとれば，それはソナー自体の技術的な研究ではない。それは，ある目標物をソナーが探知するための条件を，電子工学，音響学，海洋学，心理学的要因など，各種の要因の複合としてとらえ，簡単で有効な探知モデルを作ることを目指す。探知モデルは，後に述べる探索計画の最適化理論のサブ・モデルとなり，実施される探索計画の良し悪しを左右するので，多数の実験研究によって念入りに裏付けられねばならない。
探索理論の第2の，しかも主要な部分が探索計画の最適化理論である。探索計画を仮に全般計画と細部実施計画とに分類しよう。後者はいわば探索パターンの決定に相当する。最適なパターンは目標物の種類ばかりでなく，その所在や移動の可能性に関して事前に与えられている情報によって大いに異なり，その典型に対応して，それぞれ特有の探索パターンが考え出されている。一方，前者は，たとえば次のような問題である。一つの目標物を大洋の中で見失った。その所在の可能性は洋上に広く分布している。目標物の位置は不明だが，その確率分布はわかっているとしよう。一方，これを探索する側には限られた探索者や時間しか与えられていない。たとえば，探索者は1機の航空機で，日没以前には探索を終えなければならない，というような情況である。どのような探索手順が最も理にかなった方法であろうか。なお，探索者のセンサー能力については，先に述べたように妥当な探知モデルがすでに得られているものとする。通常，この問題は，与えられた探索期限内に目標物を発見する確率を最大にするには，洋上の各部分海面の探索にどのような時間を配分すべきか，という形式で提起される。類似の情況の下で，目標物を発見するまでの所要時間の期待値を最小にするには探索時間の配分をどのようにすればよいか，という形に問題が提起されることもある。どちらの考えに基づいたほうがよいかは情況による。これらの問いは，オペレーションズリサーチの分野で非線形計画法と呼ばれる形式の問題で，目標物が静止している場合については問題は比較的容易に解けるが，目標物が移動する場合の解法は一般により難しい。ところで，遭難船の探索にこのような理論を適用するには，海難発生の時刻とその地点の確率分布や漂流の速度分布などを推測する必要があり，そのためには，航行中の船舶や海流などに関する情報を収集・蓄積し，それらを常時最新のものに変えておくことが何よりも大切である。CASPもかなりの部分はこの種のサブ・システムから成っている。
執筆者：岸 尚
出典 株式会社平凡社「改訂新版 世界大百科事典」改訂新版 世界大百科事典について 情報