G検定 用語解説
幅優先探索とは
探索木で出発点に近い深さのノードから順にすべて調べてから次の深さへ進む探索方法。最短経路を必ず発見できる一方、調べる途中のノードを多く記憶する必要がありメモリ消費が大きい。
まず押さえる結論
幅優先探索は、G検定の「大項目2 人工知能をめぐる動向」で確認しておきたい用語です。定義だけでなく、どの場面で使う言葉か、何と混同しやすいか、問題文のどの表現で判断するかまで確認します。
情報源と編集区分
公式範囲を確認し、具体例・誤答例・判断手順は当サイトが編集。 一次情報確認日: 2026-07-03。
試験概要（公式）試験での問われ方
定義の言い換え
用語そのものではなく、説明文の一部を言い換えて出されることがあります。
似た概念との比較
同じ章の用語と入れ替えた選択肢に注意します。対象、目的、使う場面を分けます。
具体例からの判断
問題文の事例が、定義のどの部分に対応しているかを先に確認します。
誤答しやすいポイント
×AIブームと中心の対応ずれ。第一次＝探索・推論、第二次＝エキスパートシステム、第三次＝ディープラーニング。
×フレーム問題とシンボルグラウンディング問題の混同。前者は『起こりうる事柄をすべて考慮しきれない』、後者は『記号と実世界の意味を結びつけられない』。
×知識獲得のボトルネック（専門知識をルール化する作業の困難さ）をエキスパートシステムの利点と取り違える。
関連する確認問題
大項目2 人工知能をめぐる動向 / 探索・推論
経路探索において、出発点から現在のノードまでに実際にかかったコストと、そのノードからゴールまでに必要と見積もったコストとの和を評価値として用い、その値が小さいノードを優先的に展開することで、効率よく最短経路を求めようとする手法はどれか。
正解はA*アルゴリズム。出発点から現在のノードまでに実際にかかったコストと、そのノードからゴールまでに必要と見積もったコスト（ヒューリスティック）との和を評価値とし、値の小さいノードを優先的に展開することで、無駄な探索を抑えながら効率よく最短経路を求める手法である。幅優先探索は出発点に近い順に同じ深さのノードをすべて展開する方式であり、ゴールまでの見積もりコストを評価値に使わない。深さ優先探索は一つの経路を行き止まりまで深くたどる方式であり、こちらもゴールまでの見積もりコストで優先順位をつけるものではない。ブルートフォース（力任せ探索）はあらゆる可能性をしらみつぶしに調べる方式であり、コストの見積もりによってノードを優先的に展開する仕組みを持たない。問題文の「実際にかかったコストと、ゴールまでに必要と見積もったコストとの和を評価値として用い」という条件に一致するのはA*アルゴリズムだけである。
大項目2 人工知能をめぐる動向 / 探索・推論
迷路のような探索問題で、現在位置から行ける候補を木構造として広げ、同じ深さの候補を順に調べてから次の深さへ進む探索方法はどれか。
正解は「幅優先探索」である。幅優先探索は、出発点に近い順に同じ深さの候補をすべて調べてから次の深さへ進む探索方法である。深さ優先探索は一つの経路を行き止まりまで深くたどってから後戻りする方式であり、幅優先探索とは展開順序が逆になる。Mini-Max法はゲーム木で手を選ぶ際の評価値を決める考え方であり、アルファ・ベータ法はMini-Max法による探索で評価が変わらない枝を刈り込む手法である。どちらも探索木を深さの順で広げるか枝の順で進めるかという展開順序そのものを表す語ではない。
大項目2 人工知能をめぐる動向 / 探索・推論
探索木で、ある枝を行けるところまで深くたどり、行き止まりになったら戻って別の枝を調べる探索方法はどれか。
一つの枝を行けるところまで深くたどり、行き止まりに達したら手前まで戻って別の枝を調べるという展開順序そのものを指すのが、正解の「深さ優先探索」である。設問文が示す『行けるところまで深くたどる』という記述と、この展開順序の説明が直接対応する。対になる関係にある幅優先探索は、深さ方向ではなく同じ深さの候補を横並びに調べてから次の深さへ進む方式であり、展開順序が逆になる点で両者を対比させて理解しておくと判別しやすい。モンテカルロ法とSTRIPSはいずれも探索木の展開順序そのものを表す語ではなく、前者は乱数試行の統計による評価手法、後者は行動計画を記述する表現形式であって、設問が問う『たどる順序』という論点とは次元が異なる。
同じ章で確認したい用語
到達チェック
- 幅優先探索を一文で説明できる
- 同じ章の似た用語と違いを説明できる
- 問題文の具体例から、幅優先探索に関係する論点を拾える
- 関連問題を解き、誤答した選択肢の理由を確認できる
執筆: ミナト編集部（運営者情報を見る）