動的計画法

動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、最適化問題を解決するための手法の一つである。

概要

動的計画法は対象となる最適化問題を複数の部分問題に分割し、求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法である。この考え方は最適化問題における最適性原理に基づいている。最適性原理は「最適解を持つ問題の部分問題の最適解は元の最適解の部分解である」というものであり、直感的な例としては『A地点からB地点への最短経路上にC地点とD地点がある場合、C地点からD地点への最短経路は、A地点からB地点への最短経路の一部である』というものがある。

「動的計画法(dynamic programming)」という言葉は1940年代にリチャード・E・ベルマンによって最初に使われた。 動的計画法の応用としては、最短経路の問題やナップサック問題、行列の積の計算に対する応用が挙げられる。多項式時間での解法が存在しないと思われる一部の問題に対して、この方法を適用することで、擬似多項式時間では最適解を得ることができる。ネットワーク、近似アルゴリズムの分野で研究されている。

分割統治法がトップダウン的な手法であるのに対し、動的計画法はボトムアップ的な手法といえる。

例題

動的計画法の適用例を示す。

フィボナッチ数列

フィボナッチ数列とは第n項の値が第 n-1 項と第 n-2 項の和となる数列のことである。

定義を直接実装したプログラム

定義に基づいてプログラムを作成すると、次のようになる。

 int fib(n){
   if(n==0 || n==1){
     return 1;
   }else{
     return fib(n - 1) + fib(n - 2);
   }
 }

例えば、このプログラムを使ってフィボナッチ数列の第5項を求める場合を考えてみる。このプログラムは再帰的に呼び出されるので、その様子を以下に示す。

• fib(5)
• fib(4) + fib(3)
• (fib(3) + fib(2)) + (fib(2) + fib(1))
• ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
• (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

このように最終的にfib(0)とfib(1)の呼び出しに収束し、fib(0)とfib(1)の呼び出し回数の和が結果の値となる。この方法を用いたフィボナッチ数列の計算量は指数関数時間となる。

動的計画法を利用したプログラム

 int fib(n) {
   int num1 = 1, num2 = 1, tmp = 1;
   for(int i = 1; i < n; i++) {
     tmp = num1 + num2;
     num1 = num2;
     num2 = tmp;
   }
   return tmp;
 }

この場合は先ほどの実装と異なり、変数を加えてループを行っていて計算量は O(n) の多項式時間である。このように指数関数時間で行われる処理を、直前の状態をメモリに記憶することにより多項式時間で処理できるように改良できる。つまり、かかる時間を圧倒的に減らせる。

関連項目

• 分割統治法
• チャートパーサ - CYK法、アーリー法
• メモ化
• ビタビアルゴリズム
• 貪欲法