動的計画法(Dynamic Programming)

動的計画法動的計画法, DP

動的計画法とは、小さい部分問題を計算して記録しておき、より大きい問題を計算する際に利用する手法のことです。

普通に計算すると同じ計算を何度も繰り返してしまい非効率であるようなアルゴリズムも、動的計画法を利用することで高速化することができます。

いくつか具体例を見ながら、動的計画法の概念に慣れていきましょう。

フィボナッチ数列の計算

以下のような、前2つの数を足していくような並びの数列をフィボナッチ数列といいます。

1, 1, 2, 3, 5, 8, 13, 21, …

漸化式で表すと以下の通りです。

$$ a_{n+2} = a_{n+1} + a_{n} $$

これの第n項を求める方法を考えてみましょう。

動的計画法を使わないで計算する場合

ナイーブに実装すると再帰関数を利用して以下のようになります。

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

第n項を求めるために、第n-1項と第n-2項を再帰的に呼び出して計算する必要があるのですが、実は同じ計算を何度も行っているため非効率です。

第5項を求める場合を例として考えてみましょう。

フィボナッチ第5項を求める際の関数の呼び出され方

上の図を見てもらうとわかりますが、fib(5)の計算をする際に、fib(3)の計算を2回行っています。今回はfib(5)の計算なのでこの程度で済んでいますが、求めたいフィボナッチ数が大きくなればなるほど、その無駄が無視できない大きさにまでなってしまいます。

動的計画法を使う場合(メモ化再帰)

一度計算したfib(n)の結果を配列などに保存しておき、既に計算したことのある値だったら再利用することにしましょう。

これにより、無駄な計算が無くなって、かなりの高速化ができます。

int memo[100000];
int fib_dp(int n) {
    if (n <= 2) {
        return 1;
    } else {
        if (memo[n] != 0) { // 計算したことがある値だったら再利用
            return memo[n];
        } else {
            memo[n] = fib_dp(n - 1) + fib_dp(n - 2); // 計算結果をメモに保存
            return memo[n];
        }
    }
}

このような動的計画法の実装方法を、メモ化再帰などと言うことがあります。

動的計画法を使う場合(漸化式)

メモ化再帰は、再帰関数を使ってメモしていきましたが、直接配列の上で計算してしまっても構いません。

dp[ i ] := フィボナッチの第 i 項

となるよう、以下のように i が0からn-2の時まで更新してやります。

dp[ i+2 ] = dp[ i+1 ] + dp[ i ]

int dp[10000];
dp[1] = 1;
dp[2] = 1;
for (int i = 1; i < n - 1; i++) {
    dp[i + 2] = dp[i + 1] + dp[i];
}

このような、漸化式を利用した動的計画法の実装方法もあります。

ナップサック問題

動的計画法を使う有名な問題です。以下のような問に答えます。

価値が \(v_i\) 、重さが \(w_i\) で表される荷物が N 個ある。重さ B を超えないようにナップサックに入れる時、選んだ荷物の価値の合計は最大でどれだけか?

動的計画法を使わない場合

動的計画法を使わないナイーブな実装を考えてみましょう。荷物の入れ方を全探索し、重さBを超えないもので価値が最大となる時を出力すれば良いです。

荷物の選び方は、それぞれの荷物に対して「入れる or 入れない」の2通りがあるので、全体で\(2^N\)通りあります。

これは再帰関数を用いて計算することができます。 i 番目の荷物を選択するかしないかで分岐させてください。

int N, B;
int v[100], w[100];
int knapsack(int i, int b) { // i番目の荷物について考える。残り容量はb
    int ret;
    if (i == N) { // もう選ぶ荷物がない
        ret = 0;
    } else if (b < w[i]) { // i番目の荷物が入らない
        ret = knapsack(i + 1, b);
    } else {
        int use = knapsack(i + 1, b - w[i]) + v[i]; // i番目の荷物を使う時
        int no_use = knapsack(i + 1, b);            // i番目の荷物を使わない時
        ret = max(use, no_use);
    }
    return ret;
}

この場合、荷物の数Nが大きい場合、計算にかなりの時間がかかってしまいます。

動的計画法を使う場合(メモ化再帰)

先程のフィボナッチの例と同様に、動的計画法によって高速化させることができます。

ナップサックのナイーブな再帰関数も、余計な計算があるので、メモ化再帰によって高速化ができます。結果を配列に保存しておき、2回目以降は再利用をしましょう。

int N, B;
int v[100], w[100];
int memo[100][10000];
int knapsack_rec(int i, int b) {
    if (memo[i][b] != 0) { // 既に計算したことがあるなら再利用
        return memo[i][b];
    }
    int ret;
    if (i == N) {
        ret = 0;
    } else if (b < w[i]) {
        ret = knapsack_rec(i + 1, b);
    } else {
        int use = knapsack_rec(i + 1, b - w[i]) + v[i];
        int no_use = knapsack_rec(i + 1, b);
        ret = max(use, no_use);
    }
    memo[i][b] = ret; // 結果をメモ
    return ret;
}

動的計画法を使う場合(漸化式)

漸化式を使って同じ問題をどのように表現すれば良いか考えてみましょう。先程のメモ化した配列を参考にして、

dp[ i ][ b ] := 残りの重さが bまで となる i 番目までの荷物の選び方で、最大となる価値の総和

というのを漸化式を用いて表現してみましょう。

仮に最適な選び方をしたとして、dp[ i ][ b ] の値を考えてみましょう。i 番目の荷物を使う時は dp[ i-1 ][ b – w[ i ]]+v[ i ] が価値の総和の最大となり、使わない時は dp[ i-1 ][ b ] となるはずです。

よって漸化式は以下のようになります。

dp[ i ][ b ] = max(dp[ i-1 ][ b + w[ i ]]+v[ i ], dp[ i-1 ][ b ])

int dp[100][10000];
for (int i = 1; i < N + 1; i++) {
    for (int b = B; b >= 0; b--) {
        if (b + w[i] > B) {
            dp[i][b] = dp[i - 1][b];
        } else {
            dp[i][b] = max(dp[i - 1][b + w[i]] + v[i], dp[i - 1][b]);
        }
    }
}

求める答えは、 dp[N][0] になります。

ナップサックの漸化式的な解き方は他にも色々あり、

dp[ i ][ b ] := i 番目までの荷物について、重さの総和がbまでとなるもので、価値の総和の最大値

などとしても解くことができます。

動的計画法動的計画法, DP

Posted by cs-learner