G検定 用語解説
探索（幅優先・深さ優先）とは
考えられる選択肢を順にたどって解への道筋を見つける手法。第一次AIブームの中心。
まず押さえる結論
探索（幅優先・深さ優先）は、G検定の「大項目2 人工知能をめぐる動向」で確認しておきたい用語です。定義だけでなく、どの場面で使う言葉か、何と混同しやすいか、問題文のどの表現で判断するかまで確認します。
情報源と編集区分
公式範囲を確認し、具体例・誤答例・判断手順は当サイトが編集。 一次情報確認日: 2026-07-03。
試験概要（公式）試験での問われ方
定義の言い換え
用語そのものではなく、説明文の一部を言い換えて出されることがあります。
似た概念との比較
同じ章の用語と入れ替えた選択肢に注意します。対象、目的、使う場面を分けます。
具体例からの判断
問題文の事例が、定義のどの部分に対応しているかを先に確認します。
誤答しやすいポイント
×AIブームと中心の対応ずれ。第一次＝探索・推論、第二次＝エキスパートシステム、第三次＝ディープラーニング。
×フレーム問題とシンボルグラウンディング問題の混同。前者は『起こりうる事柄をすべて考慮しきれない』、後者は『記号と実世界の意味を結びつけられない』。
×知識獲得のボトルネック（専門知識をルール化する作業の困難さ）をエキスパートシステムの利点と取り違える。
関連する確認問題
大項目2 人工知能をめぐる動向 / 探索・推論
探索木を使った経路探索で、出発点に近いノードから同じ深さのノードをすべて調べ、それが終わってから一つ深い階層へ進む方法はどれか。最短経路を必ず見つけられる反面、調べる途中のノードを多く記憶しておく必要がある。
正解は幅優先探索。出発点に近い順に同じ深さのノードをすべて展開してから次の深さへ進むため、最短経路を必ず発見できるが、展開待ちのノードを多数保持するためメモリ消費が大きくなる。アルファ・ベータ法はMini-Max法によるゲーム木探索で、勝敗の評価に影響しない枝を刈り込む手法であり、深さごとに全ノードを展開する探索順序の方式ではない。モンテカルロ法はランダムな試行を多数回行い、その勝敗の統計から手を評価する手法であり、ノードを体系的に展開する探索方式ではない。深さ優先探索は一つの経路を行き止まりまで深くたどってから後戻りする方式で、幅優先探索とは対照的に記憶量は少ないが最短経路の発見は保証しない。問題文の「同じ深さのノードをすべて調べてから一つ深い階層へ進む」という展開順序に一致するのは幅優先探索だけである。
大項目2 人工知能をめぐる動向 / 探索・推論
二人零和ゲームでMini-Max法によりゲーム木を探索する際、これ以上調べても最終的な評価が変わらないと判断できる枝の探索を途中で打ち切り、無駄な計算を減らす手法はどれか。
Mini-Max法は、自分の手番では評価値を最大化し、相手の手番では評価値を最小化する行動を仮定して、双方が最善を尽くした場合の結果から現在の手を決める探索である。アルファ・ベータ法は、この探索の途中で「これ以上調べても最終的な評価は変わらない」と判断できた枝を打ち切ることで、同じ結論をより少ない計算量で導く点に特徴がある。判断の軸は、探索する対象や順序そのものを表す語か、評価の見込みから枝を刈り込む工夫を表す語かにある。トイ・プロブレムは単純化された問題群の総称、ハノイの塔はその一例となる題材、幅優先探索は展開順序の方式であり、いずれも評価の見込みで探索を打ち切る発想そのものではない。
大項目2 人工知能をめぐる動向 / 探索・推論
囲碁などのゲームで、ある局面から先の手をランダムに何度も終局までシミュレーションし、その勝敗の統計をもとに各手の有望さを評価する手法はどれか。
正解はモンテカルロ法。ある局面から先の手をランダムに何度も終局までシミュレーション（プレイアウト）し、その勝敗の統計から各手の有望さを評価する手法で、囲碁AIなどで成果を上げた。アルファ・ベータ法はMini-Max法の探索で評価が変わらない枝を刈り込む手法であり、ランダムな試行を繰り返して統計を取る手法ではない。幅優先探索は同じ深さのノードをすべて調べてから次の深さへ進む展開順序の方式であり、深さ優先探索は一つの経路を深くたどってから後戻りする方式であって、いずれもランダムなシミュレーションで手を評価するものではない。問題文の「先の手をランダムに何度も終局までシミュレーションし、その勝敗の統計」という条件に一致するのはモンテカルロ法だけである。
同じ章で確認したい用語
到達チェック
- 探索（幅優先・深さ優先）を一文で説明できる
- 同じ章の似た用語と違いを説明できる
- 問題文の具体例から、探索（幅優先・深さ優先）に関係する論点を拾える
- 関連問題を解き、誤答した選択肢の理由を確認できる
執筆: ミナト編集部（運営者情報を見る）