根Sからゴールを探す探索木がある。Sの子ノードはAとB、Aの子ノードはCとD、Cの子ノードはEであり、ゴールはBとEの2つである。同じ親をもつノードはアルファベット順に調べ、ゴールを1つ見つけた時点で探索を終える。幅優先探索と深さ優先探索に関する説明として、最も適切なものを1つ選べ。
正解と解説を見る
解説
正解 A
この問題の論点：幅優先探索と深さ優先探索の違い
ポイント
幅優先探索は根に近いゴールから順に見つけるため手数が最も少ない解が得られますが、メモリを多く使います。深さ優先探索の最初の解は最短とは限りません。
選択肢ごとの解説
- A
適切 正解
幅優先探索は、同じ深さのノードをすべて調べてから次の深さへ進みます。深さ1のAとBを調べた時点でゴールBが見つかります。手数が最も少ない解から順に見つかるのが特徴です。
- B
不適切
深さ優先探索は、1つの枝を行き止まりまでたどってから引き返します。この木ではS、A、C、Eの順に調べるため、Bより先に深さ3のゴールEが見つかります。
- C
不適切
Eは深さ3、Bは深さ1にあるため、最も近いゴールはBです。深さ優先探索は最初にたどった枝の先にあるゴールを返すので、見つかる解の手数が最も少ないとは限りません。
- D
不適切
幅優先探索は、次に調べる深さのノードをすべて保持しておく必要があり、木が深く広いほどメモリを多く使います。深さ優先探索は、いまたどっている経路の周辺だけを保持すればよいため、一般に省メモリです。
試験での狙われ方
小さな探索木でノードを調べる順序をたどらせる形や、解の最短性とメモリ使用量を2つの探索で入れ替えた選択肢で問う形がよく見られます。
参考
- G検定 試験出題範囲（シラバス2024）第1.4版 （技術分野 項目3 探索・推論）