反復深化探索

反復深化探索(反復深化深さ優先探索, ID, Iterative deepening depth-first search)は深さを制限した深さ優先探索を最大深さ0から次第に大きくしながら目的のデータが見つかるまで繰り返す探索. 手法 1. ルートノードより最大深さdを0として探索を開始. 2. 現在の最大深さdに1を加えて、深さ優先探索を行う. 3. 2.で見つからなければ再度2.を実行.見つかるまで繰り返す. 深さ優先のメモリの効率性と幅優先探索の完全性(解があったら必ず見つかる)、最適性(最も浅い解が見つかる)を備え持っているため、深さ優先探索や幅優先探索よりも理論上優れていることが多い. 毎回最大深さを1ずつ加えていき再度深さ優先探索を実行するが、このとき一つ小さい最大深さのときの深さ優先探索と同様なことを行っていて無駄に思われる.しかし実際は次の深さの探索を行うことによって増える時間の方が大きいため、繰り返し同じような探索をしている時間は大して無駄になっていない. 空間計算量は深さ優先探索を用いているため、ほぼ同様に平均分岐数bと解の深さdからO(bd)と分かる. また、時間計算量はO(b^d)となる