G検定（ジェネラリスト検定） 人工知能とその動向 練習問題 第42問: 反復深化（iterative deepening）による探索の説明として、最も適切なものはどれか。

「深さの上限を1ずつ上げながら深さ優先探索を繰り返す」説明が適切です。Poole・Mackworthの教科書（第3版）の3.5.3節によると、反復深化は上限つきの深さ優先探索を深さ1、2、3…と繰り返し、辺の数の順に経路を数え上げるので、辺の数が最も少ない解を最初に見つけます。

幅優先の最前線を記憶せずに計算し直すので記憶量は深さ優先探索程度で済み、「記憶して使い回す」「指数的に増える」とする説明は誤りです。やり直しの余分な計算は、分岐の数bに対して漸近的にb÷（b−1）倍で、b＝2で2倍、b＝3で1.5倍と、分岐が多いほど割合は小さくなります。

探索は深さの上限つきで行うので、上限を設けないとする説明も誤りです。幅優先の最適性と深さ優先の省メモリを両立する点を押さえましょう。