探索
探索（たんさく、英: search）とは、特定の制約条件を満たす物を見つけ出す行動のこと。
何か問題を解くに当たって、有効な解析的な解法を用いることのできない場合は、試行錯誤によって解を得る場合もある。
一部のアルゴリズムは、元々、機械学習と並んで人工知能の分野のアルゴリズムであるが、現在はその他の分野にも応用されている。類義語として検索（英: search）も参照。
概要
[編集]探索アルゴリズムとは、大まかに言えば、問題を入力として、考えられるいくつもの解を評価した後、解を返すアルゴリズムである。
まず解くべき問題を状態（英: state）と状態変化（行動、英: action）に分ける。 最初に与えられる状態を初期状態（英: initial state）といい、目的とする状態は最終状態（ゴール、英: final state, goal）と呼ばれる。 初期状態から最終状態に至る、状態及び状態変化の並びが解である。 将棋ならば、盤面の駒の配置と指し手の持ち駒が状態であり、交互に駒を動かすことが状態変化に当たる。
問題を解く類として研究されているアルゴリズムの多くは探索アルゴリズムである。ある問題の考えられるあらゆる解の集合を探索空間と呼ぶ。力まかせ探索や素朴な（知識を用いない）探索アルゴリズムは、探索空間を探索する手法としては最も単純で直観的である。一方、知識を用いた探索アルゴリズムはヒューリスティクスを使って探索空間の構造に関する知識を利用し、探索にかかる時間を削減しようとする。
知識を用いない探索
[編集]知識を用いない探索（英: uninformed search）アルゴリズムは、その問題の性質を考慮しない手法である。そのため汎用的に実装可能であり、抽象化のおかげで幅広い問題に同じ実装を適用可能である。問題は、探索空間が一般に非常に大きいため、問題が小さいものでもそれなりの時間がかかる点である。処理を高速化するため、知識を用いた探索だけを行う場合がある。
リスト探索
[編集]リスト探索（英: list search）アルゴリズムは、おそらく最も基本的な探索アルゴリズムである。その目的は、リストから何らかのキーを持つ要素を探すことである。計算機科学では最もよく研究されている分野であり、それらのアルゴリズムの計算量もよく研究されている。
その中でも最も単純なアルゴリズムが線型探索であり、単純にリスト上の各要素を調べていく。その実行時間は O(n) であり、n はリスト上のアイテムの数だが、どんなリストでも適用可能である。
より洗練されたリスト探索アルゴリズムとして二分探索があり、実行時間は O(log n) である。データが多ければ多いほど線型探索よりも性能がよくなるが、探索の前にソートしておく必要があり、またランダムアクセスが可能でなければならない。
特別なデータ構造を使った別の探索法として、平衡2分探索木を使った探索があり、実行時間は二分探索と同様にO(log n) である。これは、二分探索の考え方を拡張して、挿入と削除を高速化できるようにしたものである。
内挿探索は分布が偏っていないソートされた大きなリストでは二分探索よりも性能が良いが、最悪ケースでは O(n) となる。
グローバーのアルゴリズムは量子コンピュータ用アルゴリズムで、ソートされていないリストでの線型探索に対して二乗の性能向上をもたらす。しかし、量子コンピュータはまだ実用化されていない。
ハッシュテーブルもリスト探索に使われ、実行時間は平均ケースでO(1)であるが、必要とする領域は他のデータ構造よりも多く、最悪ケースでは O(n) もかかる。リスト探索のデータ構造については、ハッシュテーブルも参照されたい。
なお、線型探索、二分探索、平衡2分探索木といったリスト探索アルゴリズムの多くは、若干のコスト追加で、与えられたキー以下（あるいは以上）の全ての値を探すことができる。このような探索を「範囲探索(英: range search)」と呼ぶ。例外はハッシュテーブルであり、そのような探索を効率的には行えない。
文字列探索
[編集]文字列内のパターンを探索する。接尾辞木などのデータ構造で効率化することもある。
複数のファイルにまたがる物を全文検索という。
木探索・グラフ探索
[編集]木探索・グラフ探索共通
グラフ探索固有
- 最短経路問題
- 最小全域木
- 最大フロー問題・最小カット問題
- 巡回セールスマン問題
- 連結度
木探索（英: tree search）アルゴリズムは、探索技法の中心である。木のノードを探索するもので、最初から木が明示される場合と動的に木を生成する場合がある。基本原則は、データ構造から1つのノードを選び、その後者を調べてデータ構造に追加していく。このデータ構造の操作にあたっては、同じレベルのノードから順に見ていく幅優先探索と葉ノードまで見ていってバックトラックする深さ優先探索がある。
グラフ理論の問題の多くは、グラフ探索アルゴリズムで解くことができる。いくつかの物は木探索アルゴリズムを拡張したものと見ることもできる。
知識を用いた探索
[編集]知識を用いた探索（英: informed search）では、問題に固有のヒューリスティクス（評価関数）を補助として使う。良いヒューリスティックを使えば、探索は劇的に改善される。 知識を用いた探索アルゴリズムの多くは木探索である。最良優先探索や A* などがある。知識を用いない探索と同様、これらはグラフ向けにも拡張可能である。
メタヒューリスティクス
[編集]汎用的に使えるヒューリスティクスをメタヒューリスティクスという。
- 焼きなまし法 - 確率的探索アルゴリズムの一種
- タブーサーチ - 探索が局所解で停滞するのを防ぐ技法
- 遺伝的アルゴリズム - 探索空間を縮小させるヒューリスティクスとして進化の考え方を使う。
- 蟻コロニー最適化
- 粒子群最適化
連想配列
[編集]問題に関する知識に基づいてハッシュ関数を定義したハッシュテーブルは知識を用いたリスト探索アルゴリズムである。
敵対探索
[編集]チェスのようなゲームでは、考えられる全ての「手」で構成されるゲーム木があり、この木を使って最良の手を捜すことができる。この種の問題は、相手も自分にとって最良の手を選択すると想定するという興味深い特徴がある。そのため、ゲームを行う人工知能などでは、ミニマックス法、探索木の刈り込み、アルファ・ベータ法といった特徴的な探索アルゴリズムを使う。
制約充足
[編集]制約充足問題を解くアルゴリズムも探索アルゴリズムの一種である。この場合、経路を探し出すのではなく、一連の変数群の値の組合せを探す。変数の処理は任意の順序で可能であるため、木探索アルゴリズムでは効率的ではない。解法には問題の自由度を利用した組合せ最適化やバックトラッキングが使われる。バックトラッキングでの一般的な技法として制約伝播（英: constraint propagation）がある。他にも競合を最小化する局所探索アルゴリズムもある。
関連分野
[編集]関連項目
[編集]- 検索
- 選択アルゴリズム
- ノーフリーランチ定理
- 秘書問題 - 不完全な情報を伴うオンライン探索問題の一種であり、統計的な最適化戦略。
- 捜索
- ソート - 一部の探索アルゴリズムで必須となる。
- レコメンダシステム
関連図書
[編集]- 宝崎隆祐, 飯田耕司：「捜索理論における確率モデル」、コロナ社、ISBN 978-4339028331（2019年3月）。※ORの意味での探索理論である。
- 今野紀雄：「量子探索 ―量子ウォークが拓く最先端アルゴリズム- 」、近代科学社、ISBN 978-4764906303（2021年3月2日）。
- 阪田義隆：「クリギング入門 - 空間データ推定の確率論的アプローチ -」、コロナ社、ISBN 978-4339052756（2021年4月5日）。※ORの意味での探索理論である。