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