反復深化深さ優先探索
IDDFSは深さ優先探索のメモリ効率と幅優先探索の完全性(分岐が有限の場合)を併せ持っている。ノードの深さに対応して経路コストが減少しない場合、これが最適とされている。
IDDFSの空間計算量は O ( b d ) {\displaystyle O(bd)} であり、 b {\displaystyle b} は分岐係数(英語版)、 d {\displaystyle d} は深さである。木構造の根元に近い部分を何度も調べることになるため無駄のように見えるが、ノードの多くは木構造の底辺にあるため、それほどコスト増大にはならない。
ゲーム木でIDDFSを使う場合、アルファ・ベータ枝刈りなどのヒューリスティックが反復によって改善されていき、最も深い探索でのスコアの推定値がより正確になるという利点がある。また、探索順序を改善することができるため、探索をより高速に行えるという利点もある(前の反復で最善とされた手を次の反復で最初に調べることでアルファ・ベータ法の効率が良くなる)。
また、このアルゴリズムは応答性がよいという利点もある。初めの反復では d {\displaystyle d} が小さいので高速に完了する。このためこのアルゴリズムは素早く大まかな結果を示しつつ、 d {\displaystyle d} を深くすることでそれをさらに洗練させていくことができる。チェスプログラムのような対話型プログラムでは、任意の時点で探索を打ち切って、その時点で最善と思われる手を示すことができるという利点がある。これは通常の深さ優先探索では不可能である。