深さ優先探索

グラフやツリー構造を探索する際、あるノードから枝をたどり、行けるところまで深く進んでから戻る手法です。未探索の枝がある限り、現在のノードからさらに深く進むことを優先します。

この手法は、迷路の脱出やパズルの解法などで使われる基本的な探索アルゴリズムです。スタックというデータ構造を用いて、最後に訪れたノードを記録し、行き止まりになったら前の状態に戻るという処理を行います。メモリ消費が比較的少ないのが特徴です。

G検定では、AIの探索問題の基礎として出題されます。すべてのノードを網羅的に探索するアルゴリズムの一つであり、幅優先探索との比較が重要です。幅優先探索が近いノードから順に広げるのに対し、深さ優先探索は端まで一直線に進むという違いを区別できるようにしておきます。