定義と重要性
探索アルゴリズムとは、データ構造内から特定の条件を満たす要素や解を見つけるための手続きである。コンピュータ科学における基礎的な問題の一つであり、情報検索、データベース管理、人工知能、ネットワークルーティングなど幅広い応用分野で中心的な役割を果たす。探索問題の本質は、候補空間から目的の要素を効率的に特定することにあり、アルゴリズムの選択はシステム全体の性能に直接的な影響を与える。
計算量と性能指標
時間計算量
時間計算量は、入力サイズnに対してアルゴリズムの実行時間がどのように増加するかを漸近的に評価する指標である。Big-O記法を用いて表現され、線形探索ではO(n)、二分探索ではO(log n)など、アルゴリズムの特性に応じて異なる。最良、平均、最悪の各ケースで計算量が異なる場合があり、実用的な評価には平均的な性能が重要となる。
空間計算量
空間計算量は、アルゴリズムの実行に必要なメモリ容量を入力サイズの関数として評価する。再帰的実装ではコールスタックの消費が問題となることがあり、反復的実装と比較してトレードオフが存在する。例えば、深さ優先探索は再帰の深さに比例した空間を必要とする一方、幅優先探索は探索木の幅に比例した空間を必要とする。
データ構造との関係
探索アルゴリズムの効率は、使用するデータ構造に強く依存する。配列はランダムアクセスに優れるが、挿入や削除が非効率である。連結リストは動的な操作に適するが、ランダムアクセスができない。ハッシュテーブルは平均的にO(1)の探索を実現するが、衝突処理やメモリ使用量に課題がある。探索木（二分探索木、B木など）は、データの動的変更と効率的な探索を両立するために設計された構造である。
線形探索
原理と実装
線形探索は、データ構造の先頭から順に要素を比較し、目的の値が見つかるか末尾に達するまで続ける単純な手法である。疑似コードは以下の通り: 配列arrと目標値targetに対して、i=0からarr.length-1まで繰り返し、arr[i]==targetならiを返し、見つからなければ-1を返す。実装が容易であり、データがソートされていない場合やデータ量が小さい場合に適する。
平均・最悪計算量
最悪計算量はO(n)であり、目標値が存在しない場合や末尾にある場合に発生する。平均計算量もO(n)で、目標値が各位置に等確率で存在すると仮定するとn/2回の比較が必要となる。最良計算量はO(1)で、目標値が先頭にある場合である。
改良手法（自己組織化リストなど）
自己組織化リストは、頻繁にアクセスされる要素をリストの先頭に移動することで平均探索時間を改善する手法である。代表的な戦略として、アクセスごとに要素を先頭に移動するMove-to-Front法や、カウンタを用いて頻度順に並べ替えるTranspose法がある。これらの手法は、アクセスパターンに偏りがある場合に特に効果的である。
二分探索
ソート済み配列での動作
二分探索は、ソート済みの配列に対して中央の要素と目標値を比較し、目標値が小さければ左半分、大きければ右半分に探索範囲を絞り込む手法である。この過程を繰り返すことで、探索範囲を指数的に縮小する。
再帰と反復実装
反復実装では、配列の範囲をleftとrightのポインタで管理し、while(left<=right)のループ内でmidを計算して比較を行う。再帰実装では、引数として探索範囲を受け取り、ベースケースとしてleft>rightの場合に-1を返す。両者とも時間計算量はO(log n)であるが、再帰実装は空間計算量がO(log n)となる一方、反復実装はO(1)である。
適用条件と限界
二分探索はデータがソートされていることが必須条件であり、動的に変化するデータに対してはソートの維持に追加コストが発生する。また、ランダムアクセスが可能なデータ構造（配列など）に限定され、連結リストでは効率的に動作しない。
二分探索木との関連
二分探索木は、二分探索の考え方を動的データ構造に拡張したものである。各ノードが左の子孫より大きく右の子孫より小さい値を持ち、挿入と削除がO(log n)（平均）で可能である。平衡二分探索木（AVL木、赤黒木など）は、最悪の場合でもO(log n)を保証する。
補間探索
原理と計算量
補間探索は、二分探索の中央値計算を改良し、目標値がソート済み配列内でどの位置に存在するかを推定する手法である。中央値を固定値とする代わりに、範囲の両端の値と目標値の線形補間により位置を計算する。データが一様分布に従う場合、平均計算量はO(log log n)と非常に高速であるが、最悪計算量はO(n)となる。電話帳や辞書など、データの分布が既知で一様に近い場合に有効である。
深さ優先探索 (DFS)
再帰とスタックによる実装
DFSは、可能な限り深く探索を進め、行き詰まったらバックトラックする手法である。再帰実装では、各ノードを訪問済みとしてマークし、未訪問の隣接ノードに対して再帰呼び出しを行う。非再帰実装では、明示的なスタックを用いて同様の動作を実現する。どちらの実装も時間計算量はO(V+E)（Vは頂点数、Eは辺数）である。
性質と応用（トポロジカルソートなど）
DFSは、サイクル検出、強連結成分分解、トポロジカルソートなどに応用される。有向非巡回グラフ(DAG)のトポロジカルソートは、各ノードの訪問完了時刻の逆順に並べることで得られる。また、木構造の探索や迷路の解探索など、パスの完全な列挙が必要な問題にも適する。
幅優先探索 (BFS)
キューによる実装
BFSは、開始ノードから近い順に探索を進める手法で、キューを使用して実装する。開始ノードをキューに追加し、キューから取り出したノードの未訪問の隣接ノードを全てキューに追加する操作を繰り返す。時間計算量はDFSと同様にO(V+E)である。
最短経路発見への応用
BFSは、重みのないグラフにおける単一始点最短経路問題に対して、最適解を保証する。各ノードへの最短距離は、探索の進行に伴って更新され、最初に到達した経路が最短となる。これは、BFSが探索の深さを段階的に増加させる性質による。
双方向探索
双方向探索は、開始ノードと目標ノードから同時にBFSまたはDFSを実行し、両方の探索が交差した時点で経路を確定する手法である。探索空間の広がりが指数関数的に増加する問題において、通常の一方向探索と比較して探索ノード数を大幅に削減できる。例えば、分岐係数b、深さdの問題では、一方向探索がO(b^d)であるのに対し、双方向探索はO(b^(d/2))となる。
バリエーションと最適化
グラフ探索のバリエーションとして、反復深化深さ優先探索(IDS)は、深さ制限付きDFSを繰り返し実行することで、DFSの空間効率とBFSの完全性を両立する。また、ヒューリスティクスを用いた最良優先探索は、探索の効率をさらに向上させる。枝刈りやメモ化などの最適化手法は、探索空間の削減に寄与する。
貪欲探索 (Greedy Best-First)
評価関数と局所最適解
貪欲探索は、各ノードに対してヒューリスティック関数h(n)を定義し、最も目標に近いと推定されるノードから優先的に探索する。評価関数はf(n)=h(n)で表され、常に最小のh値を持つノードを展開する。この手法は高速であるが、ヒューリスティック関数の不完全性により局所最適解に陥るリスクがある。例えば、8パズル問題では、誤ったマンハッタン距離の推定が最適解の発見を妨げることがある。
A*アルゴリズム
ヒューリスティック関数の設計
A*アルゴリズムは、評価関数f(n)=g(n)+h(n)を用いる。ここでg(n)は開始ノードからnまでの実際のコスト、h(n)はnから目標までの推定コストである。ヒューリスティック関数の設計は探索効率と最適性に直結し、ドメイン知識に基づく適切な関数の選択が重要となる。例えば、経路計画ではユークリッド距離やマンハッタン距離が一般的である。
許容性と単調性
許容性とは、ヒューリスティック関数が真のコストを過大評価しない性質であり、h(n)≤h*(n)（h*(n)は真のコスト）を満たす。許容性が保障される場合、A*は最適解を発見する。単調性（一貫性）は、h(n)≤c(n,m)+h(m)を全てのエッジ(n,m)について満たす性質であり、単調性が成立する場合、A*は再探索の必要がなく効率的に動作する。
応用例（経路計画、パズル解法）
A*は、ロボットの経路計画、ゲームのAI、地図アプリケーションのナビゲーションなどで広く利用される。例えば、カーナビゲーションシステムでは、道路ネットワークのグラフに対して、直線距離をヒューリスティックとしてA*を適用することで、効率的な最短経路を計算する。また、15パズルやルービックキューブなどのパズル解法にも応用される。
IDA*とその他の変種
IDA*（Iterative Deepening A*）は、A*のメモリ消費問題を解決するために開発されたアルゴリズムである。深さ制限の代わりにコスト閾値を用いた反復深化を行い、各反復で深度優先探索を実行する。メモリ使用量はO(d)と小さいが、同じ状態を複数回探索する可能性がある。その他の変種として、メモリ制限を緩和したSMA*や、双方向探索をA*に応用したものがある。
確率的探索 (ランダム化探索、シミュレーテッドアニーリング)
確率的探索は、ランダム性を導入して局所最適解からの脱出を図る手法である。シミュレーテッドアニーリングは、金属の焼きなまし過程を模倣し、初期の高温状態では広範囲の探索を促し、温度が下がるにつれて探索を収束させる。焼きなましスケジュールの設計が性能を左右し、適切な温度減少率により大域的最適解への収束確率が向上する。ナップサック問題や巡回セールスマン問題などの組合せ最適化問題に適用される。
制約充足問題における探索（バックトラッキング）
バックトラッキングは、制約充足問題(CSP)において、変数に値を順次割り当て、制約違反が発生した場合に直前の割り当てをやり直す手法である。前方チェックやアーク整合性などの枝刈り技術と組み合わせることで効率が向上する。代表的な応用例として、数独の解法、Nクイーン問題、グラフ彩色問題がある。
データベースと情報検索における探索
データベースでは、B木やハッシュインデックスを用いた高速な探索が実現される。B木はディスクI/Oを考慮した平衡木であり、範囲検索に優れる。情報検索においては、転置インデックスを用いた全文検索が標準的であり、BM25やPageRankなどのランキングアルゴリズムと組み合わせて利用される。また、近似最近傍探索(ANN)は、大規模データセットに対する高速な類似検索を実現する。
ネットワークと経路探索（Dijkstra法、Bellman-Ford法）
Dijkstra法の原理と優先度キュー
Dijkstra法は、非負の重みを持つグラフにおける単一始点最短経路を求めるアルゴリズムである。優先度キューを用いて未確定ノードの中で最小距離のノードを効率的に選択し、その隣接ノードの距離を更新する。時間計算量は、二分ヒープを用いた場合O((V+E)log V)である。GPSナビゲーションやネットワークルーティングプロトコルOSPFで利用される。
負辺対応のアルゴリズム
負の重みを含むグラフに対しては、Bellman-Ford法が使用される。このアルゴリズムは、全てのエッジに対する弛緩操作をV-1回繰り返し、さらにV回目の反復で負の閉路を検出する。時間計算量はO(VE)であり、Dijkstra法より遅いが、負辺の存在を許容する。また、負の閉路が存在しない場合に限り、SPFA(Shortest Path Faster Algorithm)が実用的な高速化手法として用いられることがある。