反復深化探索（IDDFS/IDS）徹底ガイド：仕組み・計算量・完全性・最適性と実装のコツ
エバープレイ編集部反復深化探索（Iterative Deepening Search）とは
反復深化探索（Iterative Deepening Search, IDS / IDDFS）は、深さ優先探索（Depth-First Search, DFS）と幅優先探索（Breadth-First Search, BFS）の利点を組み合わせた探索手法です。探索の深さ制限を徐々に増やしながら深さ制限付きDFS（Depth-Limited Search, DLS）を繰り返すことで、メモリ使用量を抑えつつ「浅い解を優先的に見つける」性質（幅優先に近い振る舞い）を実現します。
基本的な仕組み
反復深化探索の基本的なアイデアは単純です。深さ制限 L を 0 から始め、L を 1,2,3,... と増やしていき、毎回深さ制限付きDFSを行います。各反復で「深さ L までのノード」を深さ優先で探索し、解が見つかれば探索を停止します。こうすることで、最小の深さにある解（最短手数の解）を見つけることができます（各辺のコストが等しい場合）。
- 開始：L = 0
- 反復：深さ制限付きDFSを深さ L で実行
- 結果が見つかれば終了。見つからなければ L++ して繰り返す
疑似コード
function IDDFS(root, goal):
for depth from 0 to ∞:
found, cutoff = DLS(root, goal, depth)
if found:
return solution
if not cutoff:
return failure
function DLS(node, goal, depth):
if node is goal:
return (true, false)
if depth == 0:
return (false, true) # cutoff（これ以上深さに達した）
any_cutoff = false
for each child in expand(node):
found, cutoff = DLS(child, goal, depth - 1)
if found:
return (true, false)
if cutoff:
any_cutoff = true
return (false, any_cutoff)
（上記疑似コードはツリー探索の形式です。グラフ探索でループや重複ノードを避けるために訪問済み集合を使う場合、実装とメモリ要件が変わります。）
計算量（時間・空間）の分析
反復深化探索を評価する際に重要なパラメータは分岐率 b と解の深さ d です。
- 時間計算量（おおよその評価）: O(b^d)
- 空間計算量: 深さ優先探索に依存。再帰的な実装ではパス長に比例し O(d)（または実装により O(bd) と記述される場合もあります）。グラフ探索で探索済集合を保持する場合はその分増加します。
時間計算量の直感的な導出：深さ d の解を見つけるには、各深さ制限 i（0 ≤ i ≤ d）で深さ i までの全ノードを展開します。展開ノード数の合計は 1 + b + b^2 + ... + b^d ≈ b^{d+1}/(b-1)。最上位のレベル b^d が最も多く、定数因子（b/(b-1)）を掛けた O(b^d) になります。つまり、IDS は見かけ上は同じ深さの単一のDFSを何度か繰り返すが、大部分の計算は最終反復（深さ d）の最下層ノード展開に費やされるため、総コストは同次元の幅優先探索と同オーダーになります。実際のオーバーヘッドは b が大きいほど小さく、例えば b=10 ではオーバーヘッド係数は約 10/9 ≈ 1.11、b=2 では 2/1 = 2（すなわち2倍）程度です。
完全性と最適性
- 完全性（Completeness）：分岐率が有限であり、解の深さ d が有限であれば IDS は解を見つけます（すなわち完全）。無限深の探索空間でも、解が有限深さに存在すれば到達します。
- 最適性（Optimality）：単位辺コスト（すべてのステップのコストが等しい）を仮定すると、IDS は最小深さの解を初めに見つけるため最短解（最小手数）に関して最適です。一般の重み付き辺に対しては必ずしも最適でなく、コストに基づく最適性を必要とする場合は一様コスト探索（Uniform Cost Search）や IDA* などの変種を用います。
反復深化のメリット・デメリット
メリット
- メモリ効率が良い：BFS が必要とする O(b^d) の巨大なメモリを避け、深さ優先の利点によりメモリは深さにほぼ線形で済む（再帰実装で O(d））。
- 浅い解を早く見つける特性：各反復で浅い深さから順に探索するため、最短手数の解を保証できる（単位コストの場合）。
- 実装が比較的単純：DLS とループだけで実装できる。
デメリット
- 同じノードを何度も展開するオーバーヘッド：特に根の近くのノードは複数回展開される。
- エッジコストが非均一な問題では最適性を保証しないため、重み付き探索では不向き。
- グラフ探索で訪問済みを保持するとメモリ利得が薄れる場合がある（探索済み集合の管理が必要な場合）。
実装上の注意点と最適化
- 深さ制限付きDFSは再帰実装が自然で、スタックベースでも実現可能。再帰深さが大きくなるとスタックオーバーフローに注意する。
- 探索済みノード（visited set）を保持すると重複展開を減らせるが、これを保持するとメモリ消費が増える。ツリー探索なら訪問済みが不要だが、グラフ探索ではループ防止のために必要。
- 反復の増分は通常 1 刻みだが、問題によっては最良境界（例えば cost-bound を増やす IDA* のような戦略）が有効な場合がある。
- 大きく分岐する場合、探索順序（探索する子ノードの順番）を工夫すると解を早く見つけられることがある（ヒューリスティックな順序付け）。
応用例と変種
- 古典的AI問題：パズル（8パズルなど）や初期のゲーム探索で、深さに応じて逐次探索する用途。
- ゲーム木探索：手数に応じた探索を行うときに反復深化が使われる。特に時間制限がある探索で、各反復は常に有効な解（現在の最大深さのベストムーブ）を返せるため、局所時間枯渇時でも暫定解を出力しやすい。
- IDA*（Iterative Deepening A*）：A* の f 値（推定総コスト）の閾値を繰り返し増やすことで、IDA* はメモリ効率の良い最適探索を実現する代表例。反復深化の考え方を A* に適用したもの。
- 探索空間が非常に大きくメモリが制約される場面で有用（例えば組合せ最適化や一部のパズル）。
BFS・DFSとの比較
- BFS：最短手数を保障するがメモリ消費が O(b^d) と非常に大きくなる。深さが少しでも大きいと現実的でない。
- DFS：メモリは小さい（パス長分）だが、最短解を見つけられない可能性があり、無限深の枝に捕まるリスクがある。
- IDS：BFS と同様の最短解の保障（単位コスト）を持ちつつ、DFS ライクな低メモリで実行できるため、深さ制限が分かっていないがメモリが制約されるケースで有効。
実践上の勘所
- 分岐率 b が非常に小さい（例えば二分木程度）なら反復によるオーバーヘッドは目立つ。b が大きければオーバーヘッドは相対的に小さい。
- 探索空間がグラフでループや重複状態が多い場合は、訪問済みチェックが必須。だがその場合はメモリ利得が小さくなるため方針を検討する必要がある。
- 実時間制約がある探索（例：ゲームの思考時間）では、反復深化は各反復ごとに中間結果を保持できるため利用しやすい。
まとめ
反復深化探索は、メモリ効率と解の短さ（単位コスト時）という重要なトレードオフを上手くバランスさせる探索手法です。短所としては同一ノードの再展開が生じる点ですが、実際の計算量は最終深さの探索に支配されるため、実用上のオーバーヘッドは限定的です。探索空間の性質（分岐率、重複状態、コスト構造）を踏まえて、BFS・DFS・IDA* などと比較検討することで適切に採用できます。
参考文献
- Iterative deepening depth-first search — Wikipedia
- Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence
- Nilsson, N. J. — Artificial Intelligence: A New Synthesis（講義ノートなど）
- Russell, S. & Norvig, P., Artificial Intelligence: A Modern Approach — 教科書（IDS の解説）
- Iterative deepening A* (IDA*) — Wikipedia
投稿者プロフィール
