深さ優先探索の使用を検討するタイミングについて考えた。

再帰的な処理は多少かけるが、深さ優先探索を実装することがうまくできないことが多いので、すこしまとめてみた。

など、ステップごとに状態やルートが分岐する場合に利用。答えはYes/Noで求められると一番楽だが、最小/最大を選ぶような問題にも普通に使える。

再帰を用いるとコールスタックがオーバーフローを起こす可能性がある。また、時間計算量がノード数に比例する。スタックを用いる場合はスタックが大きくなるほどメモリ確保が難しくなってくるのでスタックを積みまくるとこっちはこっちで遅くなる。

ある要素について操作方法が数パターンしかなく、それを全要素/データについて行うことが可能/必要となる場合

この問題だとNから順にインクリメントして条件に合致するものを探す方が実装としては一番楽だと思うが、DFSの練習にはそこそこいい問題だと思う。

数値として小さいものから作られるわけではないので、リストに全部足しておくか、最小値を変数として保持し、新たにできた条件を満たす値が最小値より小さいかどうかみるなど必要。

深さ優先探索で解ける問題は、ほかの方法でも解けることも多いので、DFSにこだわる必要はないが、ロジックや実装のシンプルさや、そこからくるデバッグの簡単さなどを考えれば悪くないと思う。

たくさん分岐パターンがある方法をこれでやろうとすると大変なので、その時は違う方法を考えたほうがいいと思う。

他に何か思いついたら追記/新記事などに起こしたい。

メモやらログやら