深さ優先探索は、グラフや木構造の探索アルゴリズムの一つです。現在地から進める分岐の最も深い場所まで突き進み、行き止まりになったら一つ手前に戻って別の探索を行う特徴を持ちます。AIの経路探索やゲーム木探索、パズル問題の解法などで広く活用されています。
深さ優先探索とは
一言でいうと「迷路を解く際、行き止まりになるまでひたすら一本道を進み、進めなくなったら戻って別の道を探すアルゴリズム」です。
詳しく解説
深さ優先探索（DFS）は、データ構造のグラフや木を効率的に巡回するための基礎的なアルゴリズムです。開始ノードから出発し、子ノードの方向へ深く進めるだけ進みます。これ以上進めなくなると、直前の分岐点までバックトラック（後戻り）し、まだ未探索の枝があればそちらへ進む動作を繰り返します。内部のデータ構造としては、後入れ先出し（LIFO）の原則に従うスタック（Stack）、あるいは再帰関数呼び出しの仕組みが使われます。メモリ消費量が比較的少なく実装が簡単な点が強みであり、AI分野ではミニマックス法などと組み合わせてゲームの着手選択（ゲーム木探索）に応用されてきました。
具体例・使われ方
AIがチェスやオセロなどのゲームにおいて、自分の手と相手の返答を何手先まで読めるか計算するゲーム木探索の基本として使われます。また、迷路の自動生成や、複雑な回路配線のショートチェック、SNSの友達の繋がりを辿るグラフの連結成分の検出などにも利用されます。
似た用語との違い
幅優先探索（BFS）がスタート地点から近いノードを網羅的にすべて探索していくのに対し、深さ優先探索は一つの経路を一番奥まで深く掘り下げていく点が異なります。幅優先探索は最短経路を見つけるのに適していますがメモリを多く消費し、深さ優先探索はメモリ消費を抑えられますが必ずしも最短経路にならない特徴があります。
注意点
深さ優先探索の最大の注意点は、無限ループに陥るリスクがあることです。ループを含むグラフで過去に訪れたノードを記録（訪問済みフラグの管理）し忘れると、永遠に同じ場所を巡り続けてしまいます。また、無限に続く深い木やグラフでは、目的のデータが見つからないまま探索が終わらなくなる恐れがあるため、最大深度の制限を設けるなどの対策が必要です。