探索木を使った探索手法に関する記述として、最も適切なものはどれか。なお、各枝のコストはすべて等しいものとする。
- 1深さ優先探索で最初に見つかった解は、必ず最短経路の解になる。
- 2幅優先探索は、探索中に保持しておくノードが少ないため、メモリ使用量が小さい。
- 3幅優先探索は、一つの枝をできるだけ深く進み、行き止まりに達すると一つ前のノードに戻って別の枝を探索する。
- 4幅優先探索は、出発点に近いノードから順に調べるため最短距離の解を必ず見つけられるが、途中のノードを記憶しておく必要がありメモリを多く使う。
正解と解説を見る
正解：4
幅優先探索は出発点に近いノードから順に調べるので、解があれば最短距離の解を必ず見つけられます。ただし、調べ途中のノードを保持し続けるためメモリを多く使います。深さ優先探索は一つの枝を行き止まりまで進んでから戻る（バックトラック）ため、メモリは少なくて済みますが、最初に見つかった解が最短とは限りません。選択肢3は深さ優先探索の説明です。「幅優先＝最短解・メモリ大、深さ優先＝メモリ小・最短とは限らない」と対で覚えましょう。
根拠：探索木（幅優先探索・深さ優先探索）