IDDFS - arosh/arosh.github.com GitHub Wiki

反復深化深さ優先探索(IDDFS)について

• 幅優先探索で解けそうなオーダーだけど状態を持つための空間計算量が大きすぎるような問題に適用するとよい。
• 幅優先探索と比べてメモリの使用量は減るけど計算時間は大幅に増えるように見える。けどコピーコストが下がったりして最終的に計算時間も減ることも多い
• 「状態を変化前のものに戻す」という処理が書けるような問題が得意。「変化前のものに戻す」ために必要な情報の最悪空間計算量が「状態そのもの」を持つのと変わらないとしても、「状態そのもの」をコピーするコストと比べると、平均時間計算量が減るような問題ならなお良い。
• と言っても、最悪時間計算量が幅優先探索に比べて落ちるというわけでは無いので、時間計算量ベースでオーダーを見積もって、メモリがヤバそうだったらIDDFSに切り替えるというのが良い。
• もしかしたらステップ数の上限をフィボナッチ数のように増加させると良いかもしれない (未検証)