1 探索の深さの基礎

1.1 定義と測度

探索の深さ（search depth）とは、探索アルゴリズムにおいて、開始ノード（根ノード）から現在のノードに至るまでの経路長をエッジ数で測った指標である。木構造では根からの深さ、グラフでは出発点からの距離として定義される。深さは非負整数値で表され、開始ノード自身の深さは0、その子ノードは1、孫ノードは2と順次増加する。この値は探索の進捗度を示す基本的なパラメータであり、アルゴリズムの停止条件や資源配分の判断に用いられる。

1.2 探索空間と深さの関係

探索空間全体のサイズは、分岐因子（branching factor）と最大深さ（または解の深さ）の積で指数関数的に増大する。分岐因子をb、探索深さをdとすると、深さdまでに生成されるノード数は最悪でO(b^d)となる。そのため、深さが1増えるごとに計算量が大幅に増加する。探索空間が深いほど、完全な探索は現実的でなくなり、何らかの制約やヒューリスティクスが必要となる。

1.3 深さと幅のトレードオフ

探索アルゴリズムは深さ志向（深さ優先）と幅志向（幅優先）の間でトレードオフを有する。深さ優先探索はメモリ使用量が少ない反面、無限に深い経路に陥るリスクがある。幅優先探索は最短解を保証するが、深さが大きくなると指数関数的なメモリ消費が生じる。このトレードオフは反復深化や深さ制限などの手法で緩和される。

2 深さ優先探索（DFS）

2.1 アルゴリズムの動作原理

深さ優先探索（Depth-First Search, DFS）は、可能な限り深く進み、行き詰まると一つ前のノードに戻る（バックトラック）方式で探索を行う。探索対象のグラフや木において、現在のノードから最初の子ノードに進み、さらにその子ノードへと深く進む。子ノードがなくなれば親ノードに戻り、次の子ノードを探索する。このプロセスを再帰的または反復的に繰り返す。

2.2 再帰実装とスタック実装

再帰実装では関数呼び出しのスタックを用いて暗黙的に深さを管理する。各再帰呼び出しが現在の深さに対応し、戻り時に自動的に前の深さに復帰する。一方、スタック実装では明示的なデータ構造（スタック）を用いて未探索のノードを管理する。両者は本質的に同等だが、再帰実装はコードが簡潔、スタック実装はスタックオーバーフローの回避や深さ制限の明示的制御が容易という特性がある。

2.3 時間計算量・空間計算量

時間計算量は探索空間全体を訪問する場合O(b^d)である。空間計算量は深さに比例しO(d)である（再帰の場合はコールスタック、スタック実装ではスタックのサイズ）。幅優先探索と比較してメモリ使用量が極めて小さい点が最大の利点である。

2.4 応用例（迷路解法、パズル探索）

DFSは迷路の経路探索（行き止まりまで進み戻る）や、数独などのパズル解決（バックトラッキング）に広く用いられる。迷路では壁に沿って右手を壁につけたまま進む方法はDFSの一種である。また、パズルでは解の候補を深く探索し、失敗したら戻って別の選択肢を試すバックトラッキングの基本アルゴリズムとして機能する。

3 深さ制限と反復深化

深さ制限探索（DLS）はDFSにあらかじめ最大深さ（深さ制限）を設定し、その深さを超えるノードを生成しないようにする手法である。深さ制限をLとすると、探索は深さLまでで打ち切られる。これにより無限ループを防止できるが、深さ制限が解の深さより小さいと解を見つけられない不完全性が生じる。適切な制限値の設定が課題となる。

3.2 反復深化深さ優先探索（IDDFS）

3.2.1 アルゴリズムの流れ

反復深化深さ優先探索（Iterative Deepening Depth-First Search, IDDFS）は、深さ制限を0から1ずつ増やしながらDLSを繰り返し実行する。各反復では現在の深さ制限でDLSを行い、解が見つかれば終了。見つからなければ制限を1増やして再度実行する。このプロセスを解が発見されるか、探索空間の最大深さに達するまで続ける。

3.2.2 完全性・最適性の特性

IDDFSは深さ制限が徐々に増加するため、有限の探索空間では完全性（解が存在すれば必ず発見）を保証する。また、深さ制限が最小の解の深さに達したとき最初に解を発見するため、各エッジのコストが均一であれば最適性も保証される（幅優先探索と同様）。時間計算量はO(b^d)だが、各深さでノードを再生成するオーバーヘッドがあるものの、定数倍の増加に留まる。空間計算量はO(d)であり、DFSと同等のメモリ効率を維持する。

3.3 深さ制限の動的調整手法

固定の深さ制限ではなく、探索の進行状況やヒューリスティック情報に基づいて深さ制限を動的に変更する手法がある。例えば、反復深化の各反復で深さを一定量ずつ増やす代わりに、前回の探索結果から次の制限を決定する方法（IDA*など）がある。また、深さ制限を探索木の特定の部分だけ緩和する手法も存在する。

4 探索深さに関する課題と対策

4.1 無限ループとサイクル回避

グラフ探索では閉路（サイクル）が存在すると、深さ優先探索が無限に深く進む可能性がある。対策として、訪問済みノードを記録する方法（閉塞リスト、visited set）や、深さ制限を設ける方法、パス上の重複をチェックする方法がある。木構造ではサイクルが存在しないためこの問題は発生しない。

4.2 深さ上限の設定基準

適切な深さ上限の設定は、探索の完全性と効率に直結する。既知の最大深さ（例えばゲームの終了条件や問題の最大手数）があればそれを上限とする。未知の場合は、反復深化のように動的に上限を増やすか、ヒューリスティックに基づいて仮の上限を設定し、解が見つからなければ緩和する。現実的な時間制約やメモリ制約も考慮する必要がある。

4.3 メモリ制約下での深さ管理

メモリが限られている環境では、深さ優先探索の空間計算量O(d)が有利であるが、再帰の深さがスタックオーバーフローを引き起こす可能性がある。対策として、スタック実装への切り替え、テール再帰の除去、深さ制限付きDFSの利用、あるいはIDA*のようなメモリ効率の良いアルゴリズムの採用が有効である。

5 深さの最適化と拡張

5.1 枝刈りと探索深さの短縮

枝刈り（pruning）は、解が存在しない経路を早期に判定して探索を打ち切る手法で、実質的な探索深さを短縮する。例えば、チェスのα-β枝刈りは有望でない手を深く探索せずに打ち切る。制約充足問題では前方検査（forward checking）やアーク整合性（arc consistency）を用いて分枝を削減する。これにより、深さが大きい領域の探索コストを大幅に削減できる。

5.2 ヒューリスティック探索（A*）における深さ

A*アルゴリズムでは、評価関数f(n)=g(n)+h(n)を用いる。ここでg(n)は開始ノードからノードnまでの実際のコスト（探索深さに相当する場合が多い）、h(n)はnから目標までの推定コストである。深さはg(n)として直接コスト計算に寄与する。A*は深さ方向の探索をヒューリスティックで誘導し、最適解を保証する（h(n)が許容的で一貫性がある場合）。深さそのものではなく、コストとしての深さが探索木の展開順序を決定する。

5.3 バックトラッキングと探索順序

バックトラッキングでは、探索の深さが進むにつれて選択肢の組み合わせが増えるため、探索順序が効率に大きく影響する。有望な順序（最小残り値ヒューリスティックなど）で子ノードを選択することで、深さ方向の不要な探索を減らせる。また、バックトラッキングにおいては「失敗が早く分かる」順序を選ぶことが重要で、これにより深さの無駄な増加を抑制できる。

6 現代的応用事例

6.1 ゲームAI（チェス、将棋の探索木）

チェスや将棋のAIでは、探索の深さが棋力に直接影響する。α-β枝刈りを用いたミニマックス探索では、限られた時間内にどこまで深く読めるかが勝敗を分ける。近年のディープラーニングを組み合わせた手法（AlphaZeroなど）でも、探索深さ（シミュレーション数に相当）は重要なパラメータである。プロ棋士と対戦できるレベルでは、通常10～20手先を読む必要がある。

6.2 Webクローラの深さ制限

Webクローラはリンクを辿ってWebページを収集するが、無限にリンクを追い続けることを防ぐため、深さ制限を設ける。多くのクローラは初期URLからのリンク深さ（クリック数）を指定し、その深さを超えたページは収集しない。これにより計算資源と収集範囲のバランスを取る。深さ制限はポリシーファイルや設定で指定され、通常3～5程度がよく使われる。

6.3 データ構造のトラバーサル（ツリー走査）

XML/HTMLのDOMツリーやファイルシステムのディレクトリ構造の走査では、深さ優先探索がよく用いられる。深さを追跡することで、インデントの深さに応じた処理（例えば階層構造の表示や変換）が可能になる。再帰的なディレクトリコピーやツリー構造のシリアライズなども、深さを意識した実装が行われる。