「探索」の版間の差分
(→グラフ探索) |
(相違点なし)
|
2013年6月30日 (日) 09:54時点における最新版
探索（たんさく）とは、何か問題を解くに当たって、有効な解析的な解法を用いることのできない、あるいは用いないときに、実際に試行錯誤することによって解を得ようとする行動のことである。 表における1次元配列の要素を調べることであり、そのためのアルゴリズムは探索アルゴリズムと呼ばれ、様々なものが考えられている。
もともと機械学習と並んで人工知能の分野のアルゴリズムであるが、現在はその他の分野にも応用されている。
探索アルゴリズムとは、大まかに言えば、問題を入力として、考えられるいくつもの解を評価した後、解を返すアルゴリズムである。おもに線形探索と2分探索とがある。
問題を解く類として研究されているアルゴリズムの多くは探索アルゴリズムである。ある問題の考えられるあらゆる解の集合を探索空間と呼ぶ。力まかせ探索や素朴な（知識を用いない）探索アルゴリズムは、探索空間を探索する手法としては最も単純で直観的である。一方、知識を用いた探索アルゴリズムはヒューリスティクスを使って探索空間の構造に関する知識を利用し、探索にかかる時間を削減しようとする。
考え方
まず解くべき問題を状態と状態変化に分ける。
将棋ならば、盤面の駒の配置と指し手の持ち駒が状態であり、交互に駒を動かすことが状態変化に当たる。 最初に与えられる状態を初期状態といい、目的とする状態は最終状態と呼ばれる。 初期状態から最終状態に至る、状態及び状態変化の並びが解である。
知識を用いない探索
知識を用いない探索（uninformed search）アルゴリズムは、その問題の性質を考慮しない手法である。そのため汎用的に実装可能であり、抽象化のおかげで幅広い問題に同じ実装を適用可能である。問題は、探索空間が一般に非常に大きいため、問題が小さいものでもそれなりの時間がかかる点である。処理を高速化するため、知識を用いた探索だけを行う場合がある。
リスト探索
リスト探索（list search）アルゴリズムは、おそらく最も基本的な探索アルゴリズムである。その目的は、リストから何らかのキーを持つ要素を探すことである。計算機科学では最もよく研究されている分野であり、それらのアルゴリズムの計算量もよく研究されている。
その中でも最も単純なアルゴリズムが線型探索であり、単純にリスト上の各要素を調べていく。その実行時間は O(n) であり、n はリスト上のアイテムの数だが、どんなリストでも適用可能である。
より洗練されたリスト探索アルゴリズムとして二分探索があり、実行時間は O(log n) である。データが多ければ多いほど線型探索よりも性能がよくなるが、探索の前にソートしておく必要があり、またランダムアクセスが可能でなければならない。
特別なデータ構造を使った別の探索法として、平衡2分探索木を使った探索があり、O(log n) の時間がかかる。これは、二分探索の考え方を拡張して、挿入と削除を高速化できるようにしたものである。
内挿探索は分布が偏っていないソートされた大きなリストでは二分探索よりも性能が良いが、最悪ケースでは O(n) となる。
グローバーのアルゴリズムは量子コンピュータ用アルゴリズムで、ソートされていないリストでの線型探索に対して二乗の性能向上をもたらす。しかし、量子コンピュータはまだ実用化されていない。
ハッシュテーブルもリスト探索に使われ、平均ケースで定数時間しかかからないが、必要とする領域は多く、最悪ケースでは O(n) もかかる。リスト探索のデータ構造については、ハッシュテーブルも参照されたい。
なお、線型探索、二分探索、平衡2分探索木といったリスト探索アルゴリズムの多くは、若干のコスト追加で、与えられたキー以下（あるいは以上）の全ての値を探すことができる。このような探索を「範囲探索(range search)」と呼ぶ。例外はハッシュテーブルであり、そのような探索を効率的には行えない。
木探索
木探索（tree search）アルゴリズムは、探索技法の中心である。木のノードを探索するもので、最初から木が明示される場合と動的に木を生成する場合がある。基本原則は、データ構造から1つのノードを選び、その後者を調べてデータ構造に追加していく。このデータ構造の操作にあたっては、同じレベルのノードから順に見ていく幅優先探索と葉ノードまで見ていってバックトラックする深さ優先探索がある。木探索の他の例として、反復深化深さ優先探索、深さ制限探索、双方向探索、均一コスト探索などがある。
グラフ探索
グラフ理論の問題の多くは、グラフ探索アルゴリズムで解くことができる。例としては、ダイクストラ法、クラスカル法、最近傍法、プリム法などがある。これらは木探索アルゴリズムを拡張したものと見ることもできる。 また、連結度に関するアルゴリズムにおいて最大隣接順序や最小次数順序が用いられる。
知識を用いた探索
知識を用いた探索（informed search）では、問題に固有のヒューリスティクスを補助として使う。よいヒューリスティックを使えば、探索は劇的に改善される。
知識を用いたリスト探索アルゴリズムとしてよく知られているものは数少ない。例えば、問題に関する知識に基づいてハッシュ関数を定義したハッシュテーブルがそうである。知識を用いた探索アルゴリズムの多くは木探索用である。最良優先探索や A* などがある。知識を用いない探索と同様、これらはグラフ向けにも拡張可能である。
敵対探索
チェスのようなゲームでは、考えられる全ての「手」で構成されるゲーム木があり、この木を使って最良の手を捜すことができる。この種の問題は、相手も自分にとって最良の手を選択すると想定するという興味深い特徴がある。そのため、ゲームを行う人工知能などでは、ミニマックス法、探索木の刈り込み、アルファ・ベータ法といった特徴的な探索アルゴリズムを使う。
制約充足
制約充足問題を解くアルゴリズムも探索アルゴリズムの一種である。この場合、経路を探し出すのではなく、一連の変数群の値の組合せを探す。変数の処理は任意の順序で可能であるため、木探索アルゴリズムでは効率的ではない。解法には問題の自由度を利用した組合せ最適化やバックトラッキングが使われる。バックトラッキングでの一般的な技法として制約伝播（constraint propagation）がある。他にも競合を最小化する局所探索アルゴリズムもある。
その他
- 文字列探索 - 文字列内のパターンを探索する。接尾辞木などのデータ構造で効率化することもある。
- 遺伝的アルゴリズム - 探索空間を縮小させるヒューリスティクスとして進化の考え方を使う。
- ソート - 一部の探索アルゴリズムで必須となる。
- 焼きなまし法 - 確率的探索アルゴリズムの一種
- タブーサーチ - 探索が局所解で停滞するのを防ぐ技法
- 最小コスト探索
- 山登り法
- NegaScout
- MTD(f)
- レコメンダシステム
