読者です 読者をやめる 読者になる 読者になる

再帰処理を高速化するには

最近いろんなアルゴリズムを学んでいるのですが、
何かしらの問題を解くときにバックトラックなどで検索してしまうと答えは出るけど非常に遅い。
二乗的に増えていくので当然ですが、この遅さを何とかしないといけない。

そこで、幅優先探索とかメモ化再帰とか動的計画法がでてくる。

幅優先探索は迷路とか2次元で可視化できるぐらいだとわかりやすいけどそれ以上の可能性の出てくるもの、例えば10人の家をどの順番で回ったら効率的かとか だとよくわからなくなる。(というか私の頭では理解できなくなる)
なのでそこはメモ化再帰というか動的計画法で計算量を減らすことが出来る。

総当りしたら答えが出るのは当然で、どうやって計算量を減らすかが頭を使うところなんだなぁと痛感。

あと、ちょっと話がそれるけど再帰処理を少しでも早くするのなら再帰メソッドの先頭で弾くより再帰呼び出しをする前に弾いたほうが断然早いね。
これを変えただけでぐっと早くなったのは驚いた。

広告を非表示にする