反復深化探索とは？
反復深化探索とは、深さの上限を1、2、3と少しずつ増やしながら、そのつど深さ優先探索をやり直す手法。深さ優先の少ないメモリ使用量と、幅優先が持つ「最も浅い解を先に見つける」性質を両立させることを狙う。
はんぷくしんかたんさく
反復深化探索の意味
深さの上限を1、2、3と少しずつ増やしながら、そのつど深さ優先探索をやり直す手法。深さ優先の少ないメモリ使用量と、幅優先が持つ「最も浅い解を先に見つける」性質を両立させることを狙う。
反復深化探索の具体例
解が深さ5にある木で、まず深さ1まで、次に深さ2まで、と探索を繰り返す。同じ浅い節点を何度も訪れることになるが、木の節点数は深くなるほど急増するため、繰返しによる無駄は全体の一部にとどまる。
反復深化探索は試験でどう引っ掛けられる？
「同じ場所を何度も調べるから遅い」と判断しがちだが、枝分かれが多い木では最深の1回分が支配的になり、幅優先と同程度の計算量で済む。利点はメモリ使用量が深さに比例する程度に収まる点にある。
反復深化探索と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。