最終更新日：2026年9月23日
gk search classical_ai cheatsheet
まず結論
幅優先探索（BFS）・深さ優先探索（DFS）・A*は、どの候補から調べるかが違います。
| 手法 | どこから調べる？ | G検定の判断キーワード |
|---|---|---|
| 幅優先探索（BFS） | 浅い階層から順に | 最短ステップ、キュー |
| 深さ優先探索（DFS） | 1本の経路を深く | 深く進む、スタック |
| A* | 有望な候補を優先 | g(n) + h(n)、ヒューリスティック |
特にA*は、すでにかかったコストと、ゴールまでの推定コストを合わせて探索する点が重要です。
直感的な説明
迷路で考えると分かりやすいです。
BFS
スタート地点から、1歩で行ける場所 → 2歩で行ける場所 → 3歩で行ける場所、のように近いところから同心円状に探します。
DFS
1つの道を、行けるところまで深く進むイメージです。行き止まりになれば戻って別の道を試します。
A*
A*は、ここまでの移動コストとゴールまであとどれくらいかかりそうかの両方を見て、有望そうな経路を先に調べます。
定義・仕組み
幅優先探索（Breadth-First Search）
BFSは、探索木・グラフの浅い階層から順番に探索します。一般にキュー（FIFO）を使います。
各辺のコストが同じ場合、BFSは最小ステップ数の解を見つけられます。一方、各階層の候補を多く保持するため、探索空間が大きいとメモリ消費が増えやすくなります。
深さ優先探索（Depth-First Search）
DFSは、1つの枝を深くたどってから戻る探索です。一般にスタック（LIFO）や再帰を使います。
途中の候補を大量に保持しなくてよいため、BFSよりメモリを抑えやすい場合があります。ただし、最短経路を保証しないことや、無限に深い探索空間では解にたどり着けない場合がある点に注意します。
A*
A*では、各候補ノード n について、f(n) = g(n) + h(n) を使います。
- g(n)：スタートから現在位置までの実コスト
- h(n)：現在位置からゴールまでの推定コスト
- f(n)：ゴールまでの見積もり総コスト
f(n) が小さい候補を優先して探索します。h(n) がヒューリスティック（heuristic）です。
適切なヒューリスティックを使うことで、ゴールと無関係な候補を減らしながら探索できます。
いつ使う？（得意・不得意）
BFS
- 各移動コストが同じ迷路
- 最小ステップ数を求めたい
- 解が比較的浅い位置にありそう
注意：候補が急増するとメモリを多く使います。
DFS
- メモリを抑えて探索したい
- 解が深い場所にある可能性がある
- とにかく1つの解を見つけたい
注意：最短経路とは限らず、深い枝へ入り込みすぎることがあります。
A*
- 地図上の経路探索
- ゴールまでの距離など、良いヒューリスティックを作れる
- 総当たりより有望な候補を優先したい
G検定ひっかけポイント
BFSなら必ず最短経路？
❌ どんな重み付きグラフでも最小コストになる
⭕ 各辺のコストが同じ場合などに、最小ステップ数の解を得られる
DFSは最短経路に強い？
❌ 深く進むので最短経路を効率よく見つける
⭕ DFSは最短経路を保証しない
A*のh(n)は実コスト？
❌ h(n)＝スタートから現在位置までの実コスト
⭕ g(n)が実コスト、h(n)がゴールまでの推定コスト
A*＝機械学習？
❌ データから学習するニューラルネットワーク手法
⭕ ヒューリスティックを使う探索アルゴリズム
ヒューリスティックを機械学習で作る場合はありますが、A*そのものは探索手法です。
まとめ（試験直前用）
- BFS＝浅いところから、キュー
- DFS＝1本を深く、スタック
- A*＝g(n) + h(n)
- g(n)＝ここまでの実コスト
- h(n)＝ゴールまでの推定コスト
- BFSの最短保証には辺コストなどの条件がある
- DFSは最短経路を保証しない
まず全体像を確認したい場合は、探索と推論もあわせて確認してください。