① 人工知能の基礎と動向 ／ 3. 探索・推論
幅優先探索とは
幅優先探索とは、探索木を浅い階層から順に、横方向へたどる探索手法です。最短経路を必ず見つけられる一方、メモリ消費が大きい点が特徴です。
この用語はG検定シラバスの「3. 探索・推論」に含まれます。 章全体の用語は用語解説①（全54語）にまとまっています。
一言でいうと
浅いところから順番に、横に広げながら調べていく探索方法です。最短経路が必ず見つかります。
探索の順序
まず初期状態から1手で到達できる状態をすべて調べ、次に2手で到達できる状態をすべて調べる——という順に進みます。探索木を階層ごとに横に舐めていくイメージです。
長所と短所
浅い階層から順に調べるため、ゴールを最初に見つけた時点でそれが最短経路になります。これが幅優先探索の最大の利点です。
ただし、次に調べる候補をすべて記憶しておく必要があるため、階層が深くなるほどメモリ消費が急激に増えるという弱点があります。この点は深さ優先探索と対になるので、必ず対比で覚えてください。
どんなときに向くか
最短経路を知りたい場合や、ゴールが浅い位置にあると見込める場合に向きます。迷路の最短ルート探索が典型例です。
逆に、探索木が非常に横に広い場合は記憶すべき候補が膨大になるため不利になります。その場合は深さ優先探索を検討します。
混同しやすい用語との違い
| 用語 | ポイント |
|---|---|
| 幅優先探索 | 浅い階層から横に探索。最短経路を保証／メモリ消費大 |
| 深さ優先探索 | 1本の枝を深くたどる。メモリ効率よい／最短経路は保証しない |
🎯 G検定での押さえどころ
- 最短経路を必ず見つけられる（各辺のコストが等しい場合）
- メモリ消費が大きい
- 深さ優先探索との対比で押さえる
⚠️ よくある誤りの選択肢
- 「幅優先探索はメモリ効率に優れる」→ 誤り。メモリ消費が大きい点が弱点です
- 「幅優先探索では最短経路が見つかるとは限らない」→ 誤り。必ず最短経路が見つかります
関連する用語
ご利用にあたって 本ページの内容は、JDLAが公開しているG検定シラバス2024や公式テキストなど、一般に公開されている情報をもとに独自に整理・解説したものです。実際の試験の出題内容を示すものではなく、また合格を保証するものでもありません。制度・法令・試験要項は変更されることがあるため、最新の情報は必ずJDLA公式サイトでご確認ください。