深さ優先探索（DFS）の特徴

問題

深さ優先探索（Depth-First Search）に関する次の記述のうち、誤りを1つ選べ。

深さ優先探索（DFS）は、探索木において、行けるところまで（一番深く）進み、行き止まりに到達したら一つ前の分岐点に戻って（バックトラック）別の道を進むアルゴリズムです。

現在探索している経路の情報だけを記憶しておけば良いため、幅優先探索（BFS）に比べてメモリ消費が少ないのが大きな利点です。

一方で、最初に見つけたゴールが必ずしも最短経路とは限らず、無限ループに陥る危険性もあるため、用途によって使い分けが必要です。

1. 深さ優先探索は一つの道を奥まで探索し、行き止まりで戻る方式である。

正しい：深さ優先探索の基本動作です。一つの経路を徹底的に深く掘り下げ、限界まで行くと一つ手前の分岐点に戻って別の経路を試します。

2. 深さ優先探索はメモリ消費が少ない。

正しい：深さ優先探索は現在探索中の経路（ノードの系列）のみをメモリに保持すればよいため、幅優先探索よりもメモリ効率が良く、探索空間が広い場合に有利です。

3. 深さ優先探索は常に最短経路を保証する。

誤り：深さ優先探索は「最初に見つかったゴール」を返すため、他にさらに短い経路が存在していてもそれに気づけません。したがって、最短経路は保証されません。

4. 深さ優先探索は迷路探索などで利用される。

正しい：迷路を解く際のように、「とりあえず進めるだけ進み、行き止まりなら戻って別の道を行く」というアプローチに合致するため、パズルや迷路の探索でよく利用されます。

← 前の問題次の問題 →

📚 より詳細を学びたい方へ