検索アルゴリズム：種類、性能、用途

基本的な分類と例

代表的な分類には、次のようなものがある。

• 線形探索：各要素を順番に調べる。単純で追加の構造を必要としない一方、n個の項目に対する時間計算量はO(n)である。
• 二分探索などの分割統治型探索：整列済みの集合を対象とし、残りの探索空間を急速に縮小する。ランダムアクセスが可能な場合、対数的な振る舞いを示す。
• ハッシュに基づく検索：ハッシュ関数によりキーをバケットへ対応付ける。実用上は平均して定数時間で検索できることが多い。ハッシュテーブルを参照。
• 木構造および索引による検索：平衡木やデータベース索引を用いて、範囲問合せや順序付き検索を行う。

グラフとAIにおける探索

対象領域がノードと辺からなるネットワークである場合、探索は経路や到達可能な状態を見つける。幅優先探索（BFS）と深さ優先探索（DFS）は、重みなしグラフにおける標準的な手法である。ダイクストラ法とA*は、これらの考え方を重み付き探索やヒューリスティックによって導かれる探索へ拡張したものである。人工知能や計画問題では、ヒューリスティック探索や近似探索が完全性と速度を交換し、非常に大規模または連続的な空間での解の発見を可能にする。

性能、トレードオフ、要件

手法ごとに、整列済みデータ、ランダムアクセス、補助構造のために利用可能なメモリなど、異なる前提条件がある。主なトレードオフには、時間と空間の関係、前処理時間と問合せ時間の関係、平均時性能と最悪時保証の関係がある。たとえば索引やキャッシュはメモリを消費する代わりに問合せを高速化し、索引やハッシュテーブルの構築は後続の検索を速くする。多くの探索手法は、入力サイズに応じてコストがどのように増加するかを表すため、ビッグO記法で解析される。

用途と注目すべき点

検索アルゴリズムは、データベース問合せ、ウェブ検索、スペルチェック、経路制御、ゲノム配列の照合、ロボットやゲームにおけるリアルタイムの経路計画を支えている。探索アルゴリズムは整列アルゴリズムとは異なるが、両者はしばしば連携する。整列済みのデータは、比較に基づく検索をより高速にするためである。大規模システムで実用的に実装する際には、並行性、分散、耐障害性も考慮しなければならない。

検索手法を選ぶ際には、データの構造と予想される問合せパターンを理解することが不可欠である。ごく小さな集合には単純な線形走査で十分な場合がある一方、大規模なシステムでは、許容可能な性能を実現するため、通常は索引、ハッシュ、または特化したグラフ探索戦略が利用される。