動的計画法の基本と実践方法を試してみた

プログラミング

動的計画法とは、再帰的なロジックを、計算結果を都度記録するロジックで代替することで、計算速度を向上させるテクニックです。
競技プログラミングのテクニックの一つなのですが、高度なアルゴリズムを実装する開発だけではなく普通の業務システム開発にも応用できそうなので、紹介します。

今回は、フィボナッチ数列の計算を例に挙げます。
再帰的に処理した場合、数列が1つ増える度に呼び出し量が2倍になるため、オーダはO^2となります。また、再帰的に関数を呼び出すとその分メモリ(スタック)を消費するため、異常終了するリスクも高くなります。
しかし、動的計画法を用いた場合は、数列が1つ増えても計算が1回増えるだけなので、オーダはOとなります。
実際に45項目を計算した結果、再帰呼び出しでは約11000ミリ秒を要しましたが、動的計画法の場合は1ミリ秒未満でした。

【スペック・動作環境】

・OS:Windows8.1 64bit
・CPU:Inter(R) Core(TM) i5-4210U CPU @ 1.70GHz 2.40GHz
・メモリ:8.00GB
・ディスク:SSD 128GB
・言語:java8
・IDE:Eclipse Oxygen

【確認用プログラム】

【実行結果】


いかがでしたでしょうか。

業務システム開発に携わっている身としては競技プログラミングは少し縁遠い存在なのですが、再帰呼び出しは業務システム開発でも使うことがあります。
(直近ではGUIの開発で使いましたし、現在趣味で作っているプログラムでも再帰呼び出しの箇所が存在します)
再帰呼び出しを使用するとどうしても重くなったり異常終了したりすることがあるので、そのような場合に動的計画法の使用を検討できると実装の幅が広がると思いました。

コメント

タイトルとURLをコピーしました