すべてのノードが子ノードを3つずつもつ探索木があり、根の深さを0として、深さ4のノードが末端である。ゴールは、深さ4のノードのうち最も左にある1つだけである。同じ親をもつ子ノードは左から順に調べ、ノードを1つ調べるたびにゴールかどうかを判定する。幅優先探索と深さ優先探索のそれぞれで、ゴールを見つけるまでに調べるノードの数（根とゴールを含む）の組み合わせとして、最も適切なものを1つ選べ。
正解と解説を見る
解説
正解 A
この問題の論点：深いゴールまでの探索ノード数
ポイント
ゴールが深い所にあるとき、幅優先探索は浅いノードをすべて調べてからでないと到達できません。その代わり、最も浅いゴールを必ず見つけます。
選択肢ごとの解説
- A
適切 正解
幅優先探索は浅い順に調べるため、深さ0〜3の1＋3＋9＋27＝40個を調べた後、深さ4の最初のノードでゴールに達し、41個です。深さ優先探索は左端を一直線に下るので、深さ0〜4の5個で済みます。
- B
不適切
2つの探索の性質が逆です。一直線に深く進むのが深さ優先探索で、同じ深さのノードを調べ尽くしてから次の深さへ進むのが幅優先探索です。
- C
不適切
81は深さ4にあるノードの数（3の4乗）です。幅優先探索は深さ4の最初のノードでゴールに当たるため、深さ4のノードをすべて調べるわけではありません。
- D
不適切
121は深さ0〜4のノードの総数（1＋3＋9＋27＋81）です。ゴールが最後に調べる右端のノードならどちらも121個になりますが、この問題のゴールは左端にあります。
試験での狙われ方
幅優先探索は最短の解を見つけられるがメモリを多く使い、深さ優先探索はメモリが少なくて済むが最短の解とは限らない、という対比が基本です。
参考
- G検定 試験出題範囲（シラバス2024）第1.4版 （技術分野 項目3 探索・推論）