探索
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/01/15 02:36 UTC 版)
何か問題を解くに当たって、有効な解析的な解法を用いることのできない場合は、試行錯誤によって解を得る場合もある。
一部のアルゴリズムは、元々、機械学習と並んで人工知能の分野のアルゴリズムであるが、現在はその他の分野にも応用されている。類義語として検索（英: 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)」と呼ぶ。例外はハッシュテーブルであり、そのような探索を効率的には行えない。
文字列探索
文字列内のパターンを探索する。接尾辞木などのデータ構造で効率化することもある。
複数のファイルにまたがる物を全文検索という。
- 1 探索とは
- 2 探索の概要
- 3 木探索・グラフ探索
- 4 制約充足
固有名詞の分類
品詞の分類
- >> 「探索」を含む用語の索引
- 探索のページへのリンク
