動的計画法(Dynamic Programing, DP)
LeetCode, AtCoder等のプログラミングコンテストでよく出題される問題の1種で、総当たり（ブルートフォース）でコーディングを行うと指数関数的な計算量(例えば$O(2^n)$)になってしまうコードの計算量を大幅に抑える(例えば$O(n^2)$等)ことができます。
そのため、プログラミングコンテストだけではなく、普段のコーディングの際にも役に立つことがある考え方だと思います。
注意)
- 本記事では、初学者が動的計画法を使い、限られた解答時間でアルゴリズム問題を解く手順について説明します。そのため短時間で理解できる分かり易さを重視し、数学的に厳密な説明は行いません。
- 疑似コードはPythonで記述します。また、関連用語はwikipediaの記載を用いています。
- 体系的に知りたい方はこちらや、wikipediaで説明されているので、参照されたし。
- また、この記事はMITの講義も参考にしています。非常に分かり易くお勧めです。
動的計画法が初見には解り難い理由
- 動的計画法は、一般的に次のように説明されます。
例えばwikipediaの場合：定義
細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。
定義1. 帰納的な関係の利用：より小さな問題例(部分問題)の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。
定義2. 計算結果の記録：小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。
- **定義2.**計算結果の記録について、直感的には計算結果をキャッシュしておく、と理解できると思います。メモを取ると言うと直感的かと思うので、「メモ化」と呼ぶことにします。
- 問題は**定義1.**ですが、初学者には理解に苦しむところがあります。
- より小さな問題例（部分問題,Subproblem）って何？
- 何で部分問題を使って帰納的な関係を利用してより大きな問題（問題自体）を解けるの？
- どうして動的計画法が使えそうかわかるの？
- そもそも動的計画法(Dynamic Programming)という単語の意味が解らん！
- Dynamic Programmingという言葉を考えたベルマンさんは、中長期的な研究を憎悪していた国防長官から数学の研究をしていることを隠すためにこの様な名前にした1…との事なので解り難くて当然
- Dynamic Programmingという言葉を考えたベルマンさんは、中長期的な研究を憎悪していた国防長官から数学の研究をしていることを隠すためにこの様な名前にした1…との事なので解り難くて当然
これらの事を説明しながら、動的計画法の問題を解く手順を見ていきます。
#動的計画法問題解答の手順
例題：ナップザック問題
例題として、有名なナップザック問題を取り上げます。
問題：
あなたは泥棒です。時計を盗むため、時計店に忍び込みました。時計の配列を$S$で表すと、そこには様々な価格の高価な時計が$S[0],...S[i],...,S[n-1]$まで大量にありますが、あなたが持ち帰ることの出来る重さ$W$は決まっています。制約条件の制限重量$W$以内で、最も高い合計価格を求めるにはどうすればよいでしょうか？
図 １ ナップザック問題
例えば時計が1000個($n=1000$)あった場合、時計の組み合わせ全て試すと、各時計を含める、含めないの2通りを全ての時計に対して考えるため、$2^{n}=2^{1000}≒10^{301}$となり、指数関数的に膨大な計算量となります。
1.動的計画法が使える可能性があるか判断する
限られた解答時間内で問題に挑む際には、無駄な検討を避けるため、最初に動的計画法を適用できそうか否かの見当を付ける必要があると思います。
従って、ここでは動的計画法が適用できるかを証明するのではなく、短時間でこの問題に対して動的計画法を適用できそうか、という見当をつけることが目的です。
さて、動的計画法が適用できるかは、定義に書かれている事が適用できるか否かという事です。それはどうすれば確認できるでしょうか？
それは、以下の条件I.、**条件II.**が最初の数分で見当つきそうだ、となれば動的計画法を適用する候補となります。
条件I. 部分問題が解ける事
**定義1.**によると大きな問題例を分解した、部分問題が解ける事が必須になります。この「部分問題が解ける」とはどのような場合のことを言うのでしょうか？
それは、$S$を入力データの配列とすると、$S$の一部に対して、全体の解と同じ条件で解が求められることを言います。
具体的には、ナップザック問題では時計店にある数多の時計(=$S$)の中から、例えば$i$以降の時計(=$S[i:]$)だけを考えたときに、制限重量$w$の制約条件下で、ナップザックに入る最大の合計価格を求めることができる、という事です。この様に求めたい最大化や最小化する対象の値を$V[i:,w]$と書くことにします。ナップザック問題の場合、$V[i:,w]$はナップザックに入る残りの制限重量が$w$の時、時計番号$i$以降($i～n$)の合計価格の事です。
計算量は膨大になりますが、$V[i:,w]$は例題の説明で述べた通りの総当たりアプローチ（ブルートフォース）で、制限重量$w$以下になる時計の組み合わせを全て考えれば、その中で最も合計価格が大きい値として求めることが可能です。
従って、この条件は満たしているという見当がつけられそうです。
なお、配列の一部分とは、以下の3種類の部分配列のことです。
- $S[:i]$ - 配列の接頭辞(prefix)
- $S[i:]$ - 配列の接尾辞(suffix)
- $S[i:j]$ - 部分配列(subarray)
今回は例として$S[i:]$ - 配列の接尾辞(suffix)の場合を取り上げています。
条件II. 再帰的に問題が解ける事
２つ目に、条件I.で解くことの出来た部分問題は、再帰的に解けそうか、という事を確認する必要があります。これは定義1.で「帰納的な関係」と言われているものです。
再帰的に解けるという事は、一例として、$S[i:]$までの求める最大の合計価格を$V[i:]$で表すと、次のような漸化式で表せる関係が有るという事です。
$V[i:] = V[i+1:] + v_{i+1}$ ($v_{i+1}$は定数) ・・・①
つまり、$V[i:]$は$V[i+1:]$を使うことで、計算量$O(1)$で求められそうだ、という見当が付けばこの段階では良しとします。
ナップザック問題の場合ですが、この段階では制限重量を考慮すると少し複雑になるため無視して、$v_{i}$を時計$i$の価格だと考えると①により$V[i:]$の最大値を求めることができます。とは言うものの、制限重量を無視しているため単純に全時計の合計価格になりますが、制限重量は後程考慮するとして、再帰的な関係が確認できたことで、この段階では条件IIに見当がついた、とします。
2.再帰関数（又は漸化式）を考える
ここまで、上記条件I.、**条件II.**を短時間で検討することで、この問題は動的計画法で解ける可能性が高い、という見当をつけました。
そこで、いよいよ動的計画法を用いたアルゴリズムを考えます。以下説明のために式を先に、後でコードを書きますが、実際問題を解く際にはコードから考えても構いません。私の場合は式よりコードの方が考えやすく、結局問題を解くのに必要なのはコードであるため、最初からコードで考えています。
**条件II.**について、重量制限を考慮した定式化を行ってみます。例えば、今回は部分配列=接尾辞として考えているため、各時計$S[i]$を$i=n-1$から$i=0$に降順で考えていくとします。先述の通り、最初に$i=n-1$の時計をナップザックに入れる場合、入れない場合それぞれについて考える必要があります。式にすると、①を拡張して次のように表せます。
ナップザックに$i=n-1$の時計を入れる場合：
$V[n-2:,w] = V[n-1:,w-weight_{n-1}] + value_{n-1}$ ・・・③
ナップザックに$S[n-1]$を入れない場合：
$V[n-2:,w] = V[n-1:,w]$ ・・・④
ここで、$weight_{n-1}$は時計$n-1$の重さ、$value_{n-1}$は価格を表します。
上式により$V[n-2:,w]$が求まったら次は、③式、④式それぞれの場合に対して、i=n-2をナップザックに入れる場合、入れない場合を考えます。
従って、この関係を$i=0,...,n-1$すべてに渡り適用するため、③、④式を$n-2=i、n-1=i+1$で置き換えて一般化すると、次のように書けます。
ナップザックに$S[i+1]$を入れる場合：
$V[i:,w] = V[i+1:,w-weight_{i+1}] + value_{i+1}$ ・・・⑤
ナップザックに$S[i+1]$を入れない場合：
$V[i:,w] = V[i+1:,w]$ ・・・⑥
ここで、重量制限$w$は時計をナップザックに入れた場合、その重量分だけ減っていく事に注意してください。
これをpythonのコードとして書いた場合、次のようになります。
（※ここでは、分かり易さのため直接式をコードに変換したもので、実際は境界条件等を考慮する必要があります。）
# weight:各時計の重量:
# 例)weight = [10, 20, 30, 35]
# value:各時計の価格=
# 例)value = [5,12,17,20]
def V(i, w):
#時計iを含む場合:
if w >= weight[i]:
V1 = V(i+1, w-weight[i]) + value[i]
#時計iを含まない場合:
V2 = V(i+1, w)
漸化式が2つ出来ましたが、**条件I.**について考察することで、2つの漸化式を1つにまとめることが出来ます。
3.部分問題を解く再帰関数（漸化式）にする
**条件I.**では総当たり(ブルートフォース)により、時計番号$i$までで、制限重量$w$以下における最大合計価格を求めることが出来ることを考えました。そしてそれは、漸化式を用いても同様に求めることが出来るはずです。
⑤、⑥式の様に、合計価格$V[i:,w]$の値が2つあった時、制限重量$w$が同じであれば、合計価格が小さい方は最大値になり得ないため、直ちに不要だと判断できます。従って、⑤、⑥2つの漸化式は次の式にまとめることが出来ます。
$V[i:,w] = max(V[i+1:,w-weight_{i+1}] + value_{i+1}$, $V[i+1:,w]$) ・・・⑦
これで、部分問題の最大値を求める式が出来ました。
pythonで書くと以下のようになります。
# weight:各時計の重量:
# 例)weight = [10, 20, 30, 35]
# value:各時計の価格=
# 例)value = [5,12,17,20]
def V(i, w):
#時計iを含む場合:
V1 = 0
if w >= weight[i]:
V1 = V(i+1, w-weight[i]) + value[i]
#時計iを含まない場合:
V2 = V(i+1, w)
return max(V1, V2)
$V(i, w)$は呼ばれるたびに、時計$i$を含む場合、含まない場合の両方を検討しますが、同じ制限重量$w$以下で合計価格が小さい方は全体の最大価格になることはないため、$max()$により合計価格が大きい方のみ返り値に設定します。
これにより、最大値になり得ない組み合わせを$i$の時点で判断できることが解ると思います。
具体例として、制限重量$W=5$のナップザックと、次のような時計があるとします。
| 時計 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 重量 | 2 | 4 | 2 | 3 |
| 価格 | 12 | 20 | 10 | 17 |
この再帰関数呼び出しの具体例をツリーで書くと下図のようになります。
図 2 再帰呼び出しツリー
再帰関数の関数呼び出しは上から下ですが、返り値は最も深い呼び出し先から返すことになります。
それにより、制限重量は青い矢印の通り上から下に計算しますが、最大価格の算出は、赤い矢印の通り下から上に辿ることになります。各ノードには下方にある2つの子ノードからそれぞれ赤い矢印が入っていますが、右側の子ノードは$i$の時計をナップザックに入れる場合、左側の子ノードが入れない場合それぞれの$V[i:,w]$の戻り値を表します。子ノードから戻ってきた最大価格が大きい方のみが採用されて上のノードにもどされていく事で、最終的に最大価格29が得られます。
さて、ここまでで漸化式(再帰関数)を使うことで、総当たりせずに最大価格を得られる方法が解りましたが、**定義2.**のメモ化を使うことで、メモリ使用量を犠牲にする代わり、より計算量を削減することが出来ます。
4.メモ化する
図 2 再帰呼び出しツリーの$i=2$の行に、紫で囲ったノードがあります。これらのノードは、現在の時計$i$と重量制限$w$が同じ$V[i:,w]$を2回呼びだしています。即ち、このノードより子ノードの計算は全て同じであるため、最初呼び出した際にメモに記録しておけば以降の計算を省略できます。
メモのサイズはいくつ必要でしょうか？ すべての時計の重さが整数だとすると、$w$の取りうる値の範囲は$0 \leq w \leq W$であるため、メモはW+1個分必要です。$i$の取りうる値の範囲は$0 \leq i \leq n-1$であるため、$n$個分必要になります。
従って、メモのサイズは$W×(n-1)$になります。
今までは配列の境界条件を考慮していなかったのですが、ここでは配列の境界条件も考慮して、
Pythonで書けば次のようになります。
# weight:各時計の重量:
weight = [2, 4, 2, 3]
# value:各時計の価格:
value = [12,20,10,17]
n = len(value)
# ナップザックの制限容量:
W = 5
#メモを確保
memo = [[0] * (W+1) for _ in range(n)]
def V(i, w):
if i >= n:
# 配列の最後を過ぎた場合
return 0
if memo[i][w]:
# メモにある場合
return memo[i][w]
#時計iを含む場合:
V1 = 0
if w >= weight[i]:
V1 = V(i+1, w-weight[i]) + value[i]
#時計iを含まない場合:
V2 = V(i+1, w)
memo[i][w] = max(V1, V2)
return memo[i][w]
V(0, W)
5.計算量の確認
既にメモにある場合、計算はしなくてよいので、メモの数だけ再帰関数を計算すればよい事になります。従って、計算量は$O(nW)$となります。
よく横軸配列のインデックス、縦軸重さのグラフ又はテーブルで説明されることが多いのですが、私にとっては再帰関数を軸に説明した方が直感的に感じたため、このような記事を認めてみました。