動的計画法とは、再帰的なロジックを、計算結果を都度記録するロジックで代替することで、計算速度を向上させるテクニックです。
競技プログラミングのテクニックの一つなのですが、高度なアルゴリズムを実装する開発だけではなく普通の業務システム開発にも応用できそうなので、紹介します。
今回は、フィボナッチ数列の計算を例に挙げます。
再帰的に処理した場合、数列が１つ増える度に呼び出し量が２倍になるため、オーダはO^2となります。また、再帰的に関数を呼び出すとその分メモリ（スタック）を消費するため、異常終了するリスクも高くなります。
しかし、動的計画法を用いた場合は、数列が１つ増えても計算が１回増えるだけなので、オーダは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
【確認用プログラム】
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
public class FibMain { public static void main(String［］ args) { // 再帰呼び出しの場合 System.out.println("■再帰呼び出し"); long startTime1 = System.currentTimeMillis(); int result1 = fib1(45); long endTime1 = System.currentTimeMillis(); System.out.println(" 結果 ：" + result1); System.out.println(" 要したミリ秒：" + (endTime1 - startTime1)); // 動的計画法の場合 System.out.println("■動的計画法"); long startTime2 = System.currentTimeMillis(); int result2 = fib2(45); long endTime2 = System.currentTimeMillis(); System.out.println(" 結果 ：" + result2); System.out.println(" 要したミリ秒：" + (endTime2 - startTime2)); } // 再帰呼び出し static int fib1(int n) { switch (n) { case 1: return 0; case 2: return 1; default: return fib1(n - 1) + fib1(n - 2); } } // 動的計画法 static int fib2(int n) { int memo［］ = new int［1000］; memo［0］ = 0; memo［1］ = 1; for (int i = 2; i ＜ n; i++) { memo［i］ = memo［i - 1］ + memo［i - 2］; } return memo［n - 1］; } } |
【実行結果】
|
1 2 3 4 5 6 |
■再帰呼び出し 結果 ：701408733 要したミリ秒：11033 ■動的計画法 結果 ：701408733 要したミリ秒：0 |
いかがでしたでしょうか。
業務システム開発に携わっている身としては競技プログラミングは少し縁遠い存在なのですが、再帰呼び出しは業務システム開発でも使うことがあります。
（直近ではGUIの開発で使いましたし、現在趣味で作っているプログラムでも再帰呼び出しの箇所が存在します）
再帰呼び出しを使用するとどうしても重くなったり異常終了したりすることがあるので、そのような場合に動的計画法の使用を検討できると実装の幅が広がると思いました。
コメント