メインコンテンツまでスキップ

動的計画法

最後に、経路探索や自然言語処理などにも使われる動的計画法について学習します。

フィボナッチ数列​

動的計画法の説明に必ずといってもいいほどよく使われるフィボナッチ数列を例に説明していきます。

フィボナッチ数列 FnF_n ( 0,1,1,2,3,5,8,13,21,34,…0, 1, 1, 2, 3, 5, 8, 13, 21, 34,\dots )は、次のように定義されるのでした。

F0=0F1=1Fn=Fn−1+Fn−2(n≥2)\begin{aligned} &F_0 = 0 \\ &F_1 = 1 \\ &F_n = F_{n - 1} + F_{n - 2} \quad (n\geq 2) \end{aligned}

再帰を使ったフィボナッチ数列​

再帰を使ったプログラムは次のように作れました。

Open In Colab

しかし、これでは計算量が O(2n)O(2^n) なので n が小さければこれで問題ありませんが、n が大きくなると時間がかかりすぎます。このプログラムで n = 40 としたら、実行するのに 1 分もかかりました。

原因は、次の図をみるとよくわかります。同じ数字を何度も計算してしまっています。たとえば、fib(2) は 3 回も計算しています。n がさらに大きくなると大変です。

DP を使ったフィボナッチ数列​

これを解決するのが、動的計画法(Dynamic Programming)です。DP とよく言われます。

DP とは大きな問題を解くときに出てくる小さな問題の解を表に記録していき、その解を利用して次の計算を進めていくアルゴリズムのことです。

DP には大きく分けて、二種類あります。トップダウン方式とボトムアップ方式です。

トップダウン方式​

計算結果をメモ化して無駄な計算を省くのがトップダウン方式です。メモ化再帰とも呼ばれます。

配列に計算結果をメモしておいて、すでに計算してあったらその値を再利用します。

メモ化してフィボナッチ数列を解くプログラムは次のようになります。これなら、計算量は O(n)O(n) なので、n = 40 どころか n = 100 でも余裕で計算できます。

Open In Colab

ボトムアップ方式​

ボトムアップ方式は、f(2) を求めてから f(3) を求めて f(4) を求める…というように下から順番に求めていこうというものです。

プログラムは次のようになります。こちらも、計算量は O(n)O(n) です。

Open In Colab
注記

次のようにしても良いでしょう。

Open In Colab

部分和問題​

次に、部分和問題(SSP)を解いてみましょう。

部分和問題（ぶぶんわもんだい）は、計算複雑性理論・暗号理論における問題で、与えられた nn 個の整数 a1,…,ana_1,\dots,a_n から部分集合をうまく選んで、その集合内の数の和が与えられた数 NN に等しくなるようにできるかどうかを判定する問題である。NP 完全であることが知られている。 -- フリー百科事典『ウィキペディア（Wikipedia）』

例としては、3、4、6 から部分集合をうまく選んで 10 を作れるかという問題であれば、4 と 6 を足せば、10 であるのでできるという答えになります。

全探索を使う​

この問題は、全探索すれば解くことは可能です。ai(1≤n)a_i(1\leq n) を含めるか含めないかの 2 通りずつがあるので、計算量は、O(2n)O(2^n) です。説明が長くなるので、全探索のプログラムは飛ばします。

動的計画法を使う​

動的計画法を使って、部分和問題を解いていきましょう。

DP テーブルを作る​

3、4、6 から部分集合をうまく選んで 10 を作れるかという問題を考えます。

動的計画法は、表を作って考えるので次のように表を用意します。

012345678910
∅\varnothing
{a1}={3}\{a_1\}=\{3\}
{a1,a2}={3,4}\{a_1,a_2\}=\{3,4\}
{a1,a2,a3}={3,4,6}\{a_1,a_2,a_3\}=\{3,4,6\}

表の ii 行 jj 列は、{ak}(0≤k≤i)\{a_k\}(0\leq k\leq i) の中からいくつかを使って jj をつくることができるかの真偽値とします。(真は 1、偽は 0 とします)

まず 0 行目を考えます。

00 行 jj 列は、∅\varnothing の中からいくつかを使って jj をつくることができるかの真偽値となります。 0 しか作れません。

よって、次のようになります。

012345678910
∅\varnothing10000000000
{a1}={3}\{a_1\}=\{3\}
{a1,a2}={3,4}\{a_1,a_2\}=\{3,4\}
{a1,a2,a3}={3,4,6}\{a_1,a_2,a_3\}=\{3,4,6\}

1 行目を考えます。

11 行 jj 列は、{a1}={3}\{a_1\}=\{3\} の中からいくつかを使って jj をつくることができるかの真偽値となります。 0 と 3 なら作れます。

よって、次のようになります。

012345678910
∅\varnothing10000000000
{a1}={3}\{a_1\}=\{3\}10010000000
{a1,a2}={3,4}\{a_1,a_2\}=\{3,4\}
{a1,a2,a3}={3,4,6}\{a_1,a_2,a_3\}=\{3,4,6\}

次に、2 行目を考えます。

22 行 jj 列は、{a1,a2}={3,4}\{a_1,a_2\}=\{3,4\} の中からいくつかを使って jj をつくることができるかの真偽値となります。 0 と 3、4、7 が作れます。

よって、次のようになります。

012345678910
∅\varnothing10000000000
{a1}={3}\{a_1\}=\{3\}10010000000
{a1,a2}={3,4}\{a_1,a_2\}=\{3,4\}10011001000
{a1,a2,a3}={3,4,6}\{a_1,a_2,a_3\}=\{3,4,6\}

次に、3 行目を考えます。

33 行 jj 列は、{a1,a2,a3}={3,4,6}\{a_1,a_2,a_3\}=\{3,4,6\} の中からいくつかを使って jj をつくることができるかの真偽値となります。 0 と 3、4、6、7、9、10 が作れます。

よって、次のようになります。

012345678910
∅\varnothing10000000000
{a1}={3}\{a_1\}=\{3\}10010000000
{a1,a2}={3,4}\{a_1,a_2\}=\{3,4\}10011001000
{a1,a2,a3}={3,4,6}\{a_1,a_2,a_3\}=\{3,4,6\}10011011011

漸化式を作る​

表を元に漸化式を作っていきます。

ii 行目を考える時、aia_i を入れるか入れないかの二択になります。

  • aia_i を入れないときは、何も変わらないので一個上のセルの値の真偽値そのままです。つまり、ii 行 jj 列の真偽値は、i−1i-1 行 jj 列の真偽値となります。
  • aia_i を入れるときは、{ak}(1≤k≤i−1)\{a_k\}(1\leq k\leq i-1) を使って、j−aij-a_i を作ることができていれば、それに aia_i を加えることで jj を作れそうです。 例えば、33 と 44 を使って、10−6=410-6=4 が作れていれば、それに 66 を加えることで 1010 を作ることができます。 そうすると、ii 行 jj 列の真偽値は、i−1i-1 行 j−aij-a_i 列の真偽値となります。

DP表

これらをまとめると、次の漸化式が作れます。

dp[i][j]=dp[i−1][j]∨dp[i−1][j−ai]\mathit{dp}[i][j]=dp[i-1][j]\lor dp[i-1][j-a_i]

ここで、j−ai<0j-a_i<0 のことまで考えると、漸化式は次のようになります。

dp[i][j]={dp[i−1][j]if ai>j,dp[i−1][j]∨dp[i−1][j−ai]else.\mathit{dp}[i][j]= \begin{dcases} dp[i-1][j] & \text{if $a_i>j$,} \\ dp[i-1][j]\lor dp[i-1][j-a_i] & \text{else.} \end{dcases}

プログラムを作る​

まず、表を次のように初期化します。

dp[i][j]={trueif j=0,falseelse.\mathit{dp}[i][j]= \begin{dcases} \mathrm{true} & \text{if $j=0$,} \\ \mathrm{false} & \text{else.} \end{dcases}

その後、さきほど求めた漸化式に従って、表を更新していきます。

dp[i][j]={dp[i−1][j]if ai>j,dp[i−1][j]∨dp[i−1][j−ai]else.\mathit{dp}[i][j]= \begin{dcases} dp[i-1][j] & \text{if $a_i>j$,} \\ dp[i-1][j]\lor dp[i-1][j-a_i] & \text{else.} \end{dcases}

プログラムは次のようになります。計算量は、O(nN)O(nN) です。

Open In Colab

練習問題​

動的計画法における有名問題であるナップサック問題を解いてみましょう。

ナップサック問題（ナップサックもんだい、Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、nn 種類の品物（各々、価値 viv_i、重量 wiw_i）が与えられたとき、重量の合計が WW を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。同じ種類の品物を 1 つまでしか入れられない場合（xi∈{0,1}x_i\in \{0, 1\}）や、同じ品物をいくつでも入れてよい場合（xix_i は 0 以上の整数）など、いくつかのバリエーションが存在する。 -- フリー百科事典『ウィキペディア（Wikipedia）』

ここでは、xi∈{0,1}x_i\in \{0,1\} とした、0-1 ナップサック問題を解いてみてください。

ヒント

まずは先ほどと同様に表を考えます。

v1=2,v2=3,v3=6,w1=2,w2=3,w3=5,W=10v_1=2,v_2=3,v_3=6,w_1=2,w_2=3,w_3=5,W=10 として考えてみます。

ii 行 jj 列は、重さが jj 以下になるように ii 番目までの品物の中からいくつかをナップサックに入れたときの価値の最大値とします。

表は次のようになります。

012345678910
000000000000
100222222222
200233555555
3002336689911
解答

これから、漸化式を考えます。

  • ii 番目の品物を使わなければ、一個上のセルの値そのままです。つまり、ii 行 jj 列の値は、i−1i-1 行 jj 列の値です。
  • ii 番目の品物を使う場合は、ii 行 jj 列の値は、i−1i-1 行 j−wij-w_i 列の値に viv_i を足したものになりそうです。

これから、漸化式を作ると次のようになります。

dp[i][j]={dp[i−1][j]if wi>j,max(dp[i−1][j],dp[i−1][j−wi]+vi)else.dp[i][j]= \begin{dcases} dp[i-1][j] & \text{if $w_i>j$,} \\ \mathrm{max}(dp[i-1][j],dp[i-1][j-w_i]+v_i) & \text{else.} \end{dcases}

この漸化式を使うとプログラムは次のようになります。計算量は、O(nW)O(nW) です。

Open In Colab