動的計画法
出典: フリー百科事典『ウィキペディア（Wikipedia）』
コンピュータ科学の分野で動的計画法（英 Dynamic Programming）とは、解くのに時間のかかる問題を、複数の部分問題に分割することで効率的に解くアルゴリズムである。
「動的計画法(dynamic programming)」という言葉は1940年代にRichard Bellmanによって最初に使われた。 ナップサック問題等、多項式時間での解法が存在しないと思われる一部の問題に対しても、この方法を適用することで擬似多項式時間では最適解を得ることができるなどの計算機科学上興味深い性質を持ち近似アルゴリズムの分野で研究されている。
目次 |
[編集] 例題
動的計画法の適用例を示す。
[編集] フィボナッチ数列
フィボナッチ数列とは第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) の多項式時間である。このように指数関数時間で行われる処理が前の状態をメモリに記憶することにより多項式時間に変化し、処理にかかる時間が圧倒的に減少することが可能になる。
 |
この「動的計画法」は、コンピュータに関連した書きかけです。この記事を加筆して下さる人を求めています。（Portal:コンピュータ） |
