反復深化深さ優先探索
メモリに載りきらないような大規模な木を探索する場合、深さ優先探索は探索木のパスの長さが長くなりすぎて探索が終わらないという問題を抱えている。「訪れたノードを記憶する」という単純な方法は、十分なメモリ量がない場合通用しなくなるのである。また、探索対象が木ではなく一般の有向グラフである場合(特に、ループを含む場合)にも同じ問題が起こる。これは、木の深さを段階的に増やして探索する反復深化深さ優先探索で解決することができる。
下記の図を用いた場合、

グラフの左にある辺が右にある辺より先に選択され、以前訪れたノードを記憶することにより再訪しないとするならば、Aからスタートした深さ優先探索はA, B, D, F, E, C, Gという順番で訪れる。
ここで以前訪れたノードを記憶していない場合、A, B, D, F, E, A, B, D, F, Eと、A, B, D, F, Eのループに捕まって永遠にCやGに到達することはできない。
反復深化はこのループを回避し、上記のように左から右に探索が進むとすると、下記の深さにおいて下記のノードに到達する。
0: A
1: A (repeated), B, C, E
(反復深化はCをみつけていることに注意。通常の深さ優先探索では見つからない。)
2: A, B, D, F, C, G, E, F
(以前Cを見つけていることに注意。Eを別のパスでみつけていることとFでループを見つけていることにも注意。)
3: A, B, D, F, E, C, G, E, F, B
このグラフでは深さを増やしていくたびに、アルゴリズムが探索を断念して他の枝に行くまで"ABFE", "AEFB"のループが長くなる。
反復深化深さ優先探索(はんぷくしんかふかさゆうせんたんさく、英語: iterative deepening depth-first search、IDDFS)とは、探索アルゴリズムの一種であり、深さ制限探索の制限を徐々に増大させ、最終的に目標状態の深さになるまで反復するものである。各反復では深さ優先探索の順序で探索木のノードを調べるが、全体として見れば(刈り込みがない場合)、各ノードを初めて調べる順序は幅優先探索と同じ順序になる。
IDDFSを知識あり探索にしたものがIDA*(英語版)である。これは、ダイクストラ法を知識あり探索にしたものがA*であることに対応する。