深さ優先探索とは

深さ優先探索は、探索木の1つの枝をできるだけ深くたどっていく探索方法です。行き止まり（それ以上進めないノード）に着いても解がなければ、1つ前の分かれ道まで戻り、まだ調べていない枝に進みます。この後戻りをバックトラックと呼びます。迷路で「突き当たるまで進み、だめなら直前の分かれ道に戻る」というやり方と同じです。

長所

保持しておくノードが少なく済みます。いまたどっている1本の道筋と、その途中の分かれ道に残っている枝だけを覚えておけばよいからです。1つのノードから平均b本の枝が出て、最も深いところまでの深さがmなら、覚える量はおよそb×mに比例します。同じ深さのノードをすべて覚える幅優先探索（およそb^d）と比べて、深い問題でもメモリが足りなくなりにくいのが特徴です。また、解が深い位置にたくさんある問題では、早く解にたどり着くことがあります。

短所

最初に見つかった解が、手数の最も少ない解とは限りません。たまたま先に選んだ枝の奥で、遠回りの解が見つかることがあるからです。さらに、探索木が無限に深い場合や、同じ状態に何度も戻ってくる場合には、1本の枝をたどり続けて解に届かないことがあります。そこで、深さに上限を設ける深さ制限探索や、上限を少しずつ広げる反復深化探索といった工夫が使われます。

幅優先探索との関係

これから調べるノードを、幅優先探索は先に入れたものから取り出す待ち行列（キュー）で管理します。深さ優先探索は、最後に入れたものから取り出すスタックで管理します。違いは取り出す順番だけですが、最短の手数の保証とメモリの量という性質がちょうど逆になります。

覚え方

「深さ＝縦に突き進み、だめなら戻る。メモリは少ないが最短とは限らない」と覚えます。