探索アルゴリズム完全ガイド：基本概念から代表手法・計算量・実務での選択ポイント

2025年11月20日 最終更新日時 : 2025年11月20日 エバープレイ編集部

探索アルゴリズムとは — 概要と位置づけ

探索アルゴリズム（search algorithms）とは、与えられた問題空間（状態空間）内で目標状態を見つけたり、最適な解を探索したりするための手法群を指します。コンピュータサイエンスや人工知能、ロボティクス、経路探索、パズル・ゲーム、プランニングなど幅広い分野で基礎的かつ重要な役割を持ちます。探索対象は木構造やグラフで表されることが多く、ノード（状態）とエッジ（遷移や行動、コスト）から構成されます。

基本概念：状態空間・ノード・枝・評価関数

探索問題を正しく扱うには以下の基本概念を押さえる必要があります。

  • 状態（state）：問題を記述する単位（例：地図上の座標、8パズルのタイル配置）。
  • ノード（node）：探索木／グラフ上の状態を表す要素。通常、ノードは親ノードや深さ、到達コスト（g）などの情報を持ちます。
  • 枝（edge）：状態間の遷移。重み（コスト）を伴うことがある。
  • 評価関数：ノードの良さを測る尺度。代表的には g（開始からのコスト）、h（ヒューリスティック評価）、f = g + h（A*など）。
  • 枝刈り（pruning）：探索空間を減らす工夫。重複検出（visited set）やヒューリスティックによる枝刈りが含まれる。

探索アルゴリズムの分類

探索アルゴリズムは大きく「盲探索（uninformed／uninformed）＝情報を持たない」系と「有情報探索（informed／heuristic）」系に分けられます。さらに、木探索とグラフ探索（重複ノード管理の有無）や、最適性・完全性（必ず解を見つけるか、見つけた解が最適か）という観点でも区別されます。

代表的な盲探索（基本アルゴリズム）

  • BFS（幅優先探索）

    ルートから同じ深さのノードをすべて探索していく手法。解の深さが d のとき、最短手順（エッジ数）での解を保証します（全てのエッジコストが等しい場合に最短）。時間計算量・空間計算量はいずれも分岐因子 b と深さ d によって概算され、ノード数は指数的に増加します（概ね O(b^d)）。メモリ消費が大きいのが欠点。

  • DFS（深さ優先探索）

    ある分岐を深く掘り下げていく手法。空間計算量は比較的低く O(bm)（m は最大深度）ですが、解の最短性は保証されず、無限深の探索空間で無限ループに陥る可能性があります。再帰やスタックで実装します。

  • 反復深化探索（Iterative Deepening DFS, IDDFS）

    深さを制限したDFSを深さ制限を1ずつ増やして繰り返す手法。BFSと同様に最短解を見つけつつ、DFSと同等の低い空間複雑度を達成します。状態空間が非常に深いが分岐因子が一定の場合に有効です。

  • 一様コスト探索（Uniform-Cost Search）

    各ノードを g（開始からの最低コスト）に基づいて展開する手法で、非負コストのグラフに対して最小コスト解を保証します。グラフ上ではダイクストラ法と同義に扱えます。

ヒューリスティック探索（有情報探索）

問題固有の知識を使って探索を効率化するアプローチ。ヒューリスティック関数 h(n) はノード n からゴールまでの「推定コスト」を示し、良いヒューリスティックは探索ノード数を劇的に削減します。

  • A*（エースター）

    A*は f(n) = g(n) + h(n) を評価関数として最も有望なノードを展開します。h が「許容的（admissible）」である（すなわち常に実際の残コストを過小評価する）場合、A*は最適解を保証します。さらに、h が「一貫性（consistent）」であれば（任意の遷移 n→n' に対して h(n) ≤ c(n,n') + h(n')）、ノードの再展開を避けられ、実装が簡単になります。A*の時間計算量はヒューリスティックの質に強く依存し、最悪ケースでは依然として指数的です。

  • 貪欲最良優先探索（Greedy Best-First Search）

    h(n) のみを使用して評価する手法で、非常に高速にゴールに到達することがありますが、最適性は保証されません。ヒューリスティックが誤差を含む場合にゴールとは異なる方向へ誘導されるリスクがあります。

  • IDA*（Iterative Deepening A*）

    A*のメモリ使用量がボトルネックとなる場合に用いられる手法で、f 値の閾値を増加させながら深さ優先探索を反復します。メモリは線形に抑えられますが、同じノードが複数回探索されるため時間オーバーヘッドがあります。

グラフ探索に特有の注意点：重複とコスト

木（tree）を探索する場合は同じ状態が複数回現れる心配は少ないですが、グラフではサイクルや異なる経路から同一状態に到達することがあるため、「重複検出（closed set）」や「再開放（node re-opening）」の処理が必要です。コスト付きグラフでは、最短経路が後で見つかる可能性があるため、ノードの扱いを慎重に行う必要があります（例：一様コスト探索やDijkstraは重複検出を含む実装が一般的）。

計算量・評価指標（完備性・最適性・時間・空間）

  • 完備性（Completeness）：アルゴリズムが解の存在時に必ず解を見つけるか。例：BFSや一様コスト探索は条件付きで完備。
  • 最適性（Optimality）：見つけた解がコスト的に最良か。例：A*は許容的ヒューリスティックで最適性を保障する。
  • 時間計算量：典型的には分岐因子 b と深さ d に依存。BFSは O(b^d)、DFSは O(b^m)（m は最大深度）、A* はヒューリスティックに依存し最悪は指数的。
  • 空間計算量：BFSは解探索において最もメモリを消費し O(b^d) になりがち。IDA* やDFSは深さに比例するためメモリ効率がよい。

実装時の実務上のポイント

  • データ構造：オープンリスト（優先度付きキュー）、クローズドセット（ハッシュセット）を適切に用いる。
  • ヒューリスティック設計：許容性（admissible）・一貫性（consistent）を意識して設計するとA*の最適性を保てる。近似的だが計算が速いヒューリスティックを採るか、正確だが重いものを採るかのトレードオフを考える。
  • メモリ対時間のトレードオフ：メモリが制約される環境ではIDA*や遅延戦略を検討。
  • 重複状態の管理：同一状態の複数経路がある場合、どの g 値を保持するか（より小さい g を保持するなど）を明確に。
  • エッジコストの取り扱い：負コストがある場合、Dijkstra/A*は正しく動作しない（Bellman-Ford のような手法が必要）。

代表的な適用例

  • 地図／ナビゲーション（A*、Dijkstra）
  • パズル（8パズルや15パズル：IDA*がよく使われる）
  • ロボットの経路計画（ヒューリスティック＋コスト地図）
  • ゲームAI（経路探索、単純な行動決定）
  • 組合せ最適化問題の部分探索（分枝限定法やヒューリスティックによる枝刈り）
  • 大規模な情報検索は状態空間探索とは別だが、概念的に「探索」を含む（インデックスとランク学習が主体）。

よくある誤解と注意点

  • 「ヒューリスティックが良ければ常に高速」：良いヒューリスティックは確かにノード数を減らすが、計算コストが高ければトレードオフが発生する。
  • 「A*は常に高速で最適」：A*は最適性は保証するが、ヒューリスティックが弱いと探索ノード数は膨大になる。
  • 「DFSは常にメモリに優しい」：単純DFSはメモリ効率が良いが、深い探索で無駄に時間を消費するリスクがある。
  • 「ダイクストラとA*は別物」：厳密には評価関数の違い。A*で h(n)=0 とすると一様コスト探索（ダイクストラ）に等しくなる。

実務での選択基準まとめ

どのアルゴリズムを選ぶかは次の点で決まります。

  • 解の最適性が必須か（最適ならA*や一様コスト探索）
  • メモリ制約が厳しいか（厳しければIDA*やDFS系）
  • ヒューリスティック知識を設計可能か（可能ならA*や貪欲探索）
  • グラフが巨大か（外部メモリや分散探索、プルーニングや近似法を検討）

発展トピック（簡単な紹介）

  • 確率的探索：ランダム化やモンテカルロ法（MCTSなど）。ゲームAIや不確実性下で有効。
  • 局所探索／メタヒューリスティック：局所最適解から脱出するためのサイモテック法（シミュレーテッド・アニーリング、遺伝的アルゴリズム等）。
  • 学習付きヒューリスティック：機械学習でヒューリスティック関数を学習し、A*などに組み込む研究。
  • 分散・並列探索：巨大な状態空間に対して並列化や分散処理を行う手法。

まとめ

探索アルゴリズムは、状態空間の性質（分岐因子、深さ、コストの有無）や利用できる知識（ヒューリスティックの有無）、実行環境の制約（メモリや時間）を考慮して選択・設計する必要があります。基本理論（完備性・最適性・計算量）を理解した上で、具体的な応用に合わせてアルゴリズムやデータ構造、ヒューリスティックを最適化するのが実務的なアプローチです。

参考文献

カテゴリー
IT
前の記事
グラフ探索入門：BFS/DFSから最短経路アルゴリズムと実務応用まで徹底解説New!!
2025年11月20日
次の記事
レベル順探索(BFS)とは何か？概要・実装・応用・最短経路の復元まで徹底解説New!!
2025年11月20日