動的計画法

学部4年石川です。

本研究室のカスタムコンピューティング班では現在、「時空間連続動的計画法のハードウェア・アクセラレーション」という研究を行っています。
また、隔週の輪講では「Approximate Dynamic Programming」という洋書を読み進めています。
今回は、これらの基本となる動的計画法(Dynamic Programming: DP)について紹介します。

まず、DPとは計算機科学分野におけるアルゴリズムの1つであり、対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法です。
ある問題の最適な解を求めたり、計算結果を再利用して効率良く計算するなどといったことが可能です。

簡単な例として、フィボナッチ数列の一般項を求めることを考えます。
漸化式の定義:f(n) = f(n-1) + f(n-2) の通りのプログラムは次のようになります。

int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n – 1) + fib(n – 2);
}

上記の場合、fib(k)の再帰呼び出しによって計算を行うため、nが大きくなるほど指数関数的(2^n)に計算量が増加します。
これをDP(ループ)で書き直すと以下のようになります。

int dp[MAX_N + 1];
int fib(int n) {
dp[0] = 0;
dp[1] = 1;

for(int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2]; return dp[n]; } dp[i-1]とdp[i-2]を先に計算した上でdp[i]を計算しています。この場合、明らかに計算量はnに線形比例し、再帰呼び出しの場合と比べ計算量は大幅に削減されます。
これが先程述べた「計算結果を再利用して効率良く計算する」の一例です。

簡単ではありますが、以上がDPの基本的なアイディアです。

カテゴリー: 未分類