深さ優先探索とは

深さ優先探索とは、木やグラフをたどるとき、一つの道をできるだけ奥まで進み、行き止まりに来たら一歩ずつ引き返して別の道を試す探索アルゴリズムです。英語の頭文字をとってDFSとも呼ばれます。幅優先探索と並ぶ、AIの探索やA*探索の土台となる基本手法の一つなのです。

行けるところまで進んで、戻る

深さ優先探索の進み方は、迷路で片方の壁伝いにとにかく奥へ進み、突き当たったら分かれ道まで戻ってやり直す動きに似ています。この「行き止まりで引き返す」操作をバックトラックと呼びます。出発点に近い順に調べる幅優先探索とは対照的で、道を一本ずつ深掘りしていくのが持ち味。覚えておく情報が少なくて済むため、すべての可能性をもれなく試したい場面や、迷路の自動生成、パズルの解法探しなどで重宝されます。ただし最短ルートは保証しないので、目的に応じて幅優先探索と使い分けるのが定石でしょう。

深さ優先探索に関するよくある質問

深さ優先探索と幅優先探索は、どう使い分けますか？

最も少ない手数の最短ルートを確実に知りたいときは幅優先探索、使うメモリを抑えたいときや、解の候補をしらみつぶしに調べたいときは深さ優先探索が向きます。目的に合わせて選ぶのが基本です。

深さ優先探索は、私たちの身近でどう役立っていますか？

数独などのパズルを解くプログラムや、パソコンのフォルダの中をすみずみまで調べる処理、ゲームAIの先読みなどに使われています。一つの道を最後まで追い、ダメなら戻る粘り強い探し方が向く場面で活躍します。