「G検定を受けたいけど、AIの専門用語って難しそう…」 「探索アルゴリズムって聞くけど、何のことかサッパリ…」
そんな風に感じていませんか？ 大丈夫です！ この記事を読めば、AIの重要な基礎知識の一つである「幅優先探索（ふくゆうせんたんさく、BFS: Breadth-First Search）」が、初心者の方でもスッキリ理解できますよ！
G検定では、AIの基本的な仕組みやアルゴリズムに関する問題がよく出題されます。特にこの「幅優先探索」は、「深さ優先探索（DFS）」と並んで超重要！
この記事では、
- 幅優先探索って、一体どんな探し方なの？
- どんな仕組みで動いているの？（図解たっぷり！）
- 相棒の「深さ優先探索（DFS）」とは何が違うの？
- G検定で問われるポイントはどこ？
- モンテカルロ法とはどう違うの？
といった疑問に、AI初心者の方にも分かりやすく、図をたくさん使って徹底解説します！ 読み終わる頃には、「なるほど、BFSってそういうことか！」と、きっと誰かに説明したくなっているはずです。一緒にAIの世界を探検しましょう！
幅優先探索（BFS）ってなに？ 〜しらみつぶし作戦の基本〜
幅優先探索（BFS）を一言でいうと、「一番近いところから順番に、層を広げるように探していく方法」です。
例えるなら、迷路探し！
スタート地点から、まず「1歩で行けるマス」を全部チェックします。次に、そのチェックしたマスから「さらに1歩で行ける新しいマス」を全部チェック…というように、スタートに近い順に、じわじわと探索範囲を広げていくイメージです。
- ステップ1: スタート地点
- ステップ2: スタートから1マスで行ける範囲を全て探索
- ステップ3: スタートから2マスで行ける新しい範囲を全て探索
- ステップ4: スタートから3マスで行ける新しい範囲を全て探索 …ゴールが見つかるか、探索できる場所がなくなるまで続ける。
この探し方のおかげで、BFSには「もしゴールがあるなら、必ず最短距離（一番少ないステップ数）で見つけられる」という大きなメリットがあります。
BFSはどうやって動くの？ コア技術「キュー」を知ろう！
この「近い順に探索する」を実現するために、BFSでは「キュー（Queue）」という特別な道具を使います。
キューって何？
キューは、「先入れ先出し（FIFO: First-In, First-Out）」のルールでデータを管理する箱のようなものです。身近な例だと、お店のレジ待ちの行列と同じ！ 先に並んだ人（先に入れたデータ）から順番にレジに進み（先に取り出され）ますよね。
BFSでのキューの使い方
BFSでは、このキューを使って「次に行くべき場所（ノード）」を管理します。
シンプルな例で見てみよう！ 下の図のような、AからEまでの場所（ノード）があるとします。Aからスタートして、全ての場所をBFSで巡ってみましょう。（線は場所間の移動が可能であることを示します）
- ステップ0:
- 空のキューを用意します。
- 訪問済みリスト（一度訪れた場所を記録）を用意します。
- スタート地点「A」をキューに入れ、訪問済みリストにも追加します。
- キュー: [A]
- 訪問済み: {A}
- ステップ1:
- キューの先頭から「A」を取り出します。（デキュー）
- 「A」から行ける未訪問の場所を探します → 「B」と「C」が見つかりました。
- 見つけた「B」と「C」を順番にキューの末尾に入れます。（エンキュー）
- 「B」と「C」を訪問済みリストに追加します。
- キュー: [B, C]
- 訪問済み: {A, B, C}
- ステップ2:
- キューの先頭から「B」を取り出します。
- 「B」から行ける未訪問の場所を探します → 「D」が見つかりました。
- 「D」をキューの末尾に入れます。
- 「D」を訪問済みリストに追加します。
- キュー: [C, D]
- 訪問済み: {A, B, C, D}
- ステップ3:
- キューの先頭から「C」を取り出します。
- 「C」から行ける未訪問の場所を探します → 「E」が見つかりました。
- 「E」をキューの末尾に入れます。
- 「E」を訪問済みリストに追加します。
- キュー: [D, E]
- 訪問済み: {A, B, C, D, E}
- ステップ4:
- キューの先頭から「D」を取り出します。
- 「D」から行ける未訪問の場所はありません。
- キュー: [E]
- 訪問済み: {A, B, C, D, E}
- ステップ5:
- キューの先頭から「E」を取り出します。
- 「E」から行ける未訪問の場所はありません。
- キュー: [] (空になりました！)
- 訪問済み: {A, B, C, D, E}
キューが空になったので、探索終了です！ 訪問順は A → B → C → D → E となり、ちゃんとスタートに近い順（Aから1ステップのB,C、次にAから2ステップのD,E）に探索できているのが分かりますね。
BFSのメリット・デメリットまとめ
- メリット:
- 最短経路保証: 各ステップのコストが同じなら、ゴールまでの最もステップ数が少ない経路を必ず見つけられる！
- シンプル: アルゴリズムの考え方が比較的単純で理解しやすい。
- デメリット:
- メモリをたくさん使う可能性: 探索範囲が広がると、キューの中に一時的にたくさんの場所（ノード）を記憶しておく必要があり、メモリ（コンピュータの作業スペース）を大量に消費することがある。特に、一つの場所から行ける選択肢が多い場合に顕著。
ライバル登場！深さ優先探索（DFS）との違いは？
BFSのライバルとしてよく登場するのが「深さ優先探索（DFS: Depth-First Search）」です。名前の通り、こちらは「行けるところまで、まず深く掘り進んでいく」探し方です。
イメージは、迷路の一本道をとことん進む感じ！
行き止まりにぶつかったら、一つ手前の分かれ道まで戻って、別の道を進み始めます。
| 特徴 | 幅優先探索 (BFS) | 深さ優先探索 (DFS) |
| 探し方 | 広く浅く (レベルごと) | 深く狭く (一本道を突き進む) |
| 使う道具 | キュー (先入れ先出し) | スタック (後入れ先出し) or 再帰 |
| 見つける経路 | 最短経路 (ステップ数) を保証 | 最短経路を保証しない |
| メモリ使用量 | 多い傾向 (特に幅が広い場合) | 少ない傾向 (現在の経路のみ記憶) |
| 得意なこと | 最短経路探し、SNSの繋がり検索 | 経路の存在確認、迷路の踏破、パズル |
どっちを使えばいいの？
- とにかく最短経路が知りたい！ → BFS
- ゴールまでたどり着けるか知りたいだけ (経路は最短じゃなくてもOK) → DFS (メモリ効率が良い場合がある)
- 全ての経路を調べたい → DFS
G検定では、このBFSとDFSの特徴の違いや、使う道具（キュー/スタック）の違いがよく問われます！しっかり区別できるようにしておきましょう。
BFSはどんなところで活躍してるの？ 具体的な応用例
BFSの「近い順に」「最短で」探す能力は、色々な場面で役立っています。
1. 探索木（ゲームの先読みなど）
パズルや簡単なゲームの「次の一手」を考えるときに使われます。現在の状態をスタート地点として、可能な次の状態、そのまた次の状態…と木の枝のように可能性を広げて考えます。BFSを使えば、最も少ない手数でゴール（勝ちパターンなど）に到達する方法を見つけられます。
2. ハノイの塔（パズル）
有名な「ハノイの塔」パズルを解くのにもBFSが使えます。円盤の各配置を「状態」と考え、ルールに従った円盤の移動を「状態の変化」と捉えます。BFSで状態を探索していくと、必ず最小手数でパズルを解く手順を見つけることができます。
- 状態0 (スタート): (A:[3,2,1], B:[], C:[])
- 状態1 (1手目): (A:[3,2], B:[1], C:[]) や (A:[3,2], B:[], C:[1]) など
- 状態2 (2手目): … BFSはこれらの状態を近い順（少ない手数）から調べていくので、最短手順が必ず見つかる！
3. ロボットの行動計画（最短経路探索）
倉庫内を移動するロボットや、ゲームキャラクターが目的地まで障害物を避けて移動する最短経路を見つけるのに使われます。地図をマス目（グリッド）と考え、各マスをノード、隣接マスへの移動を辺とみなしてBFSで探索します。
S 1 2 3 4
1 X 3 4 5
2 3 4 X G(6)
3 X 5 6 7
4 5 6 7 8
(上記のようなイメージ。SからGまでの最短経路は6ステップ)
4. ボードゲーム (ただし限界も…)
三目並べ（○×ゲーム）のような単純なゲームなら、BFSで全ての可能な盤面を探索して「必勝法」や「最善手」を見つけることができます。
しかし、チェスや囲碁のように、選択肢（分岐）が膨大で、ゲームが非常に長く続く可能性がある複雑なゲームでは、BFSは役に立ちません。 なぜなら、考えられる全てのパターンをしらみつぶしに調べようとすると、可能性が天文学的な数になり（組合せ爆発）、世界中のコンピュータを使っても計算が終わらないからです！
（例：チェスでは1手ごとに平均約30通りの選択肢があると言われます。3手先を読むだけでも 30 x 30 x 30 = 27,000 通り！これが10手、20手…となると…想像もつきませんね！）
このような複雑なゲームでは、後述するモンテカルロ法（MCTS）など、もっと賢い探索方法が使われています。
ちょっと寄り道：BFSとモンテカルロ法の関係は？
G検定でも触れられることがある「モンテカルロ法」。これはBFSとは全く異なるアプローチです。
- BFS: 系統的に、全ての可能性をしらみつぶしに調べる。最適解（最短経路）を見つけるのが得意。
- モンテカルロ法: 確率的に、ランダムな試行（サイコロを振るような感じ）を繰り返して、「だいたいこっちの方が良さそうだ」という有望な選択肢を見つけ出す。複雑すぎて全パターン調べられない問題で活躍する。
特にゲームAIの分野では、モンテカルロ木探索（MCTS）という形で、囲碁AI「AlphaGo」などで使われ、大きな成果を上げました。
- BFS: 全ての道を平等に探索（網羅的だが、広すぎると大変）
- MCTS:有望そうな道を重点的に探索（効率的だが、最適解を見逃す可能性もある） <br>
G検定対策としては、「BFSはしらみつぶしの系統的探索、モンテカルロ法はランダム性を使った確率的探索」という根本的な違いと、それぞれの得意分野（BFS: 最短経路、MCTS: 複雑なゲームなど）を理解しておくことが重要です！
G検定対策！BFSの重要ポイントまとめ
さあ、G検定で得点するために、BFSについて最低限これだけは覚えておきましょう！
- 探し方: 近い順（レベルごと）に広く浅く探索する。
- 使う道具: キュー（FIFO: 先入れ先出し）を使う。
- 最大のメリット: 最短経路（ステップ数）を保証する（※各ステップのコストが同じ場合）。
- デメリット: メモリを大量に消費する可能性がある。
- DFSとの違い: DFSは深く探索し、スタック（LIFO: 後入れ先出し）を使う。最短経路は保証しない。
- 応用例: 最短経路検索（地図、ネットワーク）、簡単なゲームやパズルの全探索。
- 限界: 複雑なゲーム（チェス、囲碁）のような巨大な探索空間には向かない。
- モンテカルロ法との違い: BFSは系統的、モンテカルロ法は確率的（ランダム）。
これらのポイントを押さえておけば、G検定のBFS関連問題に自信を持って臨めるはずです！
まとめ：BFSはAIの第一歩！
今回は、AIの基本的な探索アルゴリズムである「幅優先探索（BFS）」について、図解を交えながらやさしく解説しました。
- BFSは「近い順に、しらみつぶし」に探す方法。
- 「キュー」を使って、レベルごとに探索を進める。
- 最短経路を見つけるのが得意だけど、メモリには注意が必要。
- DFSやモンテカルロ法との違いも理解しておこう！
BFSの考え方は、他の様々なアルゴリズムの基礎にもなっています。これを理解することは、AIの世界を探求する上での大きな一歩です。
この記事を通して、BFSの仕組みが理解でき、「誰かに説明できそう！」「G検定の問題、解けるかも！」「AIの他のアルゴリズムも面白そう！」と感じていただけたら、とても嬉しいです。
もし分からないことや、「ここはもっと知りたい！」という点があれば、ぜひコメントで教えてくださいね！ 一緒にAIの学習を楽しみましょう！
コメント