動的計画法

動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果の記録を利用して全体の問題を解く手法を総称してこう呼ぶ。

定義

細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。

帰納的な関係の利用：より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。
計算結果の記録：小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。

概要

「動的計画法(dynamic programming)」という言葉は1940年代にリチャード・E・ベルマンが最初に使いはじめ、1953年に現在の定義となった^[1]。

効率のよいアルゴリズムの設計技法として知られる代表的な構造の一つである。対象となる問題を帰納的に解く場合にくり返し出現する小さな問題例について、解を表に記録し表を埋めていく形で計算をすすめ、冗長な計算をはぶくアルゴリズムのことをいう。特定のアルゴリズムを指すのではなく、上記のような手法を使うアルゴリズムの総称である。一般的に、帰納的な定義にしたがって再帰法でアルゴリズムを作ると計算結果の再利用は行わないが、入力が単純な構造で解が等しくなることの確認が容易であるとき、同じ入力について計算済であることの確認、結果の再利用をメモリ領域を消費して行い、計算を高速化する。初歩的な説明で使われるフィボナッチ数の計算、ハノイの塔の必要移動回数の計算などでは、一次元の表（列）によって指数オーダーの計算時間を入力の数の大きさに対して線形時間に落とすことができる。（ただし、これらの級数の計算では、漸化式で参照するのは高々 2 つ前の計算結果だけなので、変数を1, 2 個用意してループすればことたりる。）効果が顕著なのが組合せ問題で、文字列の近似照合（編集距離の計算）、ナップサック問題の解法などが、二次元の表により指数時間の手続きが多項式時間に効率化される有名な例である。マルチプルアラインメントのように表が三次元以上必要になると、時間に対するトレードオフとなるメモリ領域量が大きくなりすぎるため、規模の大きな入力には実用的でなくなる。

近似アルゴリズムの分野では、多項式時間での解法が存在しないと思われる一部の問題に対して、この方法を適用することで、擬似多項式時間では最適解を得ることができる。

実現方法

以下の2種類の実現方法がある。

履歴管理を用いるトップダウン方式（英: top-down with memoization） - 分割統治法において、計算結果を記録（メモ化）して再利用する方法。再帰を併用する場合はメモ化再帰（英: memoized recursion）とも呼ばれる。
ボトムアップ方式（英: bottom-up method） - 先に部分問題を解いていく方法

適用条件

最適化問題に適用する場合、一般的に、以下の2つが適用する問題に成立していないといけない。（厳密には成立しなくても動的計画法の定義は満たせる）

部分構造最適性（英: optimal substructure）や最適性原理（英: principle of optimality）^[2]
部分問題重複性（英: overlapping subproblems）

部分構造最適性とは、以下の2条件が成立していることをさす。

部分問題も同じ最適化問題が成立している
部分問題間が独立している

部分問題を解き、それを利用して、全体の最適化問題を解く戦略のため、部分構造最適性が動的計画法には必要である。部分構造最適性の例として、最短経路問題では、A → B → C という最短経路において、A → B や B → C も最短経路でないといけない（このことは背理法により証明可能）。また、部分問題間が独立であるためには、部分問題で資源の共有があってはならない。最短経路問題では A → B と B → C で同じ辺が出現しないため（同じく背理法により証明可能）、資源の共有が発生していない。貪欲法においても厳密解を求めるのなら部分構造最適性は必要である。

部分問題重複性とは、同一の部分問題が繰り返し出現することである。動的計画法では重複する部分問題の計算結果を記録し再利用する事により計算量を削減する。

厳密なことを書くと、全体問題と部分問題は完全に同一である必要性はなく、また、部分問題間が独立でなくても、それらが何らかの計算式により依存関係を解決し結合させる方法があれば、部分構造最適性が成立しなくても動的計画法の定義を満たすアルゴリズムは作れる。しかし、そのような実用例は少ない。

例題

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

フィボナッチ数列

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

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

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

int fib(unsigned int n) {
    switch (n) {
        case 0: return 0;
        case 1: return 1;
        default: 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) の呼び出し回数の和が結果の値となる。この方法を用いたフィボナッチ数列の計算量は $O(2^{n})$ の指数関数時間となる。

動的計画法を利用したプログラム（ボトムアップ方式）

int fib(unsigned int n) {
    int memo[1000] = {0, 1}, i;
    for (i = 2; i <= n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n];
}

fib(n - 1) と fib(n - 2) を先に計算しておいた上で、fib(n) を計算している。この場合は先ほどの実装と異なり、ループ部分の計算量は O(n) の多項式時間である。このように指数関数時間で行われる処理を、計算済みの結果を記録することにより多項式時間で処理できるように改良でき、計算時間を圧倒的に減らせる。

動的計画法を利用したプログラム（トップダウン方式）

トップダウンで、メモ化を併用したやり方。fib(n) を計算するのに、fib(n - 1) と fib(n - 2) が必要だが、計算結果を配列 memo に保存して再利用している。

#include <stdbool.h>

int memo[1000] = {0, 1};
bool in_memo[1000] = {true, true};

int fib(unsigned int n) {
    if (!in_memo[n]) {
        memo[n] = fib(n - 1) + fib(n - 2);
        in_memo[n] = true;
    }
    return memo[n];
}

近年は色々なプログラミング言語がメモ化を言語レベルでサポートしている。その機能を利用した場合、より簡単に書ける場合がある。例えば Groovy の場合、@Memoized を付けることでメモ化するが、下記のように、定義を直接実装したプログラムに @Memoized を付けると動的計画法になる。

import groovy.transform.Memoized

@Memoized
int fib(int n) {
    switch (n) {
        case 0: return 0
        case 1: return 1
        default: return fib(n - 1) + fib(n - 2)
    }
}

脚注

^ Richard Bellman, An introduction to the theory of dynamic programming, The Rand Corporation, Santa Monica, Calif., 1953
^ Richard Bellman, The theory of dynamic programming, Bull. Amer. Math. Soc. 60 (1954), 503-515

[1] Richard Bellman, An introduction to the theory of dynamic programming, The Rand Corporation, Santa Monica, Calif., 1953

[bellman1954-2] Richard Bellman, The theory of dynamic programming, Bull. Amer. Math. Soc. 60 (1954), 503-515

[1]

[2]

定義

概要