12. 動的計画法¶
動的計画法 (dynamic programming) は，部分問題に分割し，その部分解を記録しながら、効率よく全体解を求める手法です。全探索では計算量が大きくなり過ぎるとき、威力を発揮します。競技プログラミングでは、動的計画法ができるかどうかで成績が大きく変わります。
12.1. フィボナッチ数¶
まず、簡単な例から動的計画法を理解しましょう。
例題（フィボナッチ数）
フィボナッチ数列の第100項(n=100)を求めてみよう
12.1.1. 再帰関数と限界¶
フィボナッチ数 \(F_n\)の漸化式をそのまま再帰関数で定義してみると、
[1]:
def fibo(n):
if n == 1 or n == 2:
return 1
return fibo(n-1) + fibo(n-2)
fibo(10) #100にすると大変
[1]:
55
このフィボナッチ関数は、n が大きくなると、実行時間が極端にかかるようになります。 計算量は、\(O((\frac{1+\sqrt{5}}{2})^n)\)で指数時間です。 実際に、n を増やしていったときの実行時間を次のように増大していきます。 (Python では、n = 35辺りが限界です。）
しかし、プログラミング技法で、指数計算時間の限界を解決することができます。
12.1.2. メモ化再帰¶
メモ化再帰は、再計算を防ぐため、一度計算した結果は、メモとして記録する手法です。 再計算の代わりにメモを使うことで効率よく計算します。
[2]:
# 計算結果を入れるメモ(大きめの配列)
memo = [0] * 1000
memo[1] = 1 # 先に n=1, n=2 の計算結果を入れておく
memo[2] = 1
def fibo(n):
if memo[n] != 0: # メモに記録されていたら計算しない
return memo[n]
# メモに結果を記録する
memo[n] = fibo(n-1) + fibo(n-2)
return memo[n]
fibo(100) # 今度は、100も計算できます。
[2]:
354224848179261915075
12.2. ループに変換する¶
フィボナッチ数の再帰関数をループ構造に変換してみます。
[3]:
memo = [0] * 1000
memo[1] = 1 # 先に n=1, n=2 の計算結果を入れておく
memo[2] = 1
def fibo(n):
for i in range(3, n+1):
memo[i] = memo[i-1] + memo[i-2]
return memo[n]
fibo(100)
[3]:
354224848179261915075
ポイントは、メモ化再帰のときと同じく、途中の計算結果を配列 (memo) に記録しています。 このように途中結果を「部分問題の解」として記録し、より大きな問題の解に活用する方法を動的計画法といいます。
DP 表
途中の計算結果を記録した表(配列)のこと
12.3. コインの問題¶
フィボナッチ数列は最初から漸化式が与えられていました。しかし、実際の問題では漸化式が最初から与えられることはありません。
動的計画法のポイント
漸化式を発見すること
漸化式を発見する方法をみていきましょう。
例題（コインの問題）
ある国の硬貨は，4 種類あり，50円, 40円, 7円, 1円 の価値を持つ。 これらの硬貨を用いて，\(x\)円払うとき、硬貨の最小枚数を求めよ。
12.3.1. 貪欲法¶
日常生活では、大きい硬貨から順番に使っていくことで、硬貨の最小枚数を考えます。 例えば、日本国内の硬貨(50,10,5,1)なら
より、127円は、合計 2+2+1+2 = 7枚。
このような方法は、アルゴリズムでは貪欲法 (greedy) と呼ばれます。 貪欲法で硬貨の枚数を求めると：
コイン(50,10,5,1)の場合
[4]:
COINS = [50, 10, 5, 1] # 硬貨の種類をセット
def greedy_coin(x):
counts = [0, 0, 0, 0]
reminder = x
for i, coin in enumerate(COINS):
counts[i] = reminder // coin
reminder %= coin
return sum(counts)
greedy_coin(127)
[4]:
7
さて、日本の硬貨のように，小さい硬貨が大きな硬貨の約数になっているのなら、貪欲法で解くことができます。ところが、今回のコインの問題のように 40 円硬貨や 7 円硬貨が登場すると、貪欲法では必ずしも最小枚数に辿り着けません。
コインの問題(50,40,7,1)
[5]:
COINS = [50, 40, 7, 1] # 硬貨の種類をセット
def greedy_coin(x):
counts = [0, 0, 0, 0]
reminder = x
for i, coin in enumerate(COINS):
counts[i] = reminder // coin
reminder %= coin
return sum(counts)
greedy_coin(127)
[5]:
11
Let’s try
コインの問題において、127円の最小枚数を探してみよう
正解（たぶん）
より、127円は、合計 0+3+1+0 = 4枚が存在する。
どうしたら，確実に最小枚数を見つけることができるのでしょうか?
12.3.2. 部分解を考える¶
動的計画法は、部分問題に分割し，「部分問題の解」から「全体問題の解」を得ることを考えます。 分割統治法に似ていますが、「部分問題の解」に計算する順序関係がある点が異なります。再帰構造 の問題と同じく、初期解から考えてみましょう。
\(dp(x)\) を \(x\) 円のときの最小枚数 (解) を表すものとします。
初期解(x = 0): 自明です。
このとき、硬貨を一枚追加して購入できる金額を考えます。 すると、dp(50), dp(40), dp(7), dp(1) の解は、それぞれ dp(0) を用いて、次のように計算できます。
これをもしS(x)がわかっていたら、次のような関係が見えきませんか？
あとは、順番に気をつけて計算します。 特に、\(dp(x)\) からみると、\(dp(x − 50) + 1\), \(dp(x − 40) + 1, ...\) のように重複して計算されます。そこで、途中の計算結果は，DP表に記録しながら、重複したときは最小値 (min) を記録するようにすれば良いでしょう。
[6]:
COINS = [50, 40, 7, 1]
def dp_coin(x):
dp = [x] * (x+51) # 最初に最大値を入れておく
dp[0] = 0 # 初期解
for p in range(0, x+1):
for coin in COINS:
dp[p+coin] = min(dp[p] + 1, dp[p+coin])
return dp[x]
dp_coin(127)
[6]:
4
これをより一般化すると、次のような関係が見えてくるはずです。
12.3.3. 再帰で考える¶
コインの最小枚数 \(coin(x)\) は，次のように漸化式にまとめることもできます。
[8]:
from functools import lru_cache
@lru_cache(300)
def coin(x):
if x <= 0 : return 0
return min(coin(x-50), coin(x-40), coin(x-7), coin(x-1)) + 1
coin(127)
[8]:
3
実は、動的計画表とメモ化再帰は、計算順序がトップダウンかボトムアップかの違いがあるだけで、アルゴリズム的な原理は同じものです。
初期解がわかっているときは
初期解から次の解が見つけられないか考え、動的計画法/再帰構造がないか探す
12.4. ナップサック問題¶
旅行カバンに何を詰めるかは、日常的に発生する問題です。そのような日常問題にモデルにした超古典的な問題「ナップサック問題」に取り組んでみましょう。
例題（ナップサック問題）
価値が \(v_i\) 重さが \(w_i\) であるような \(N\) 個のアイテムと、最大積載容量が \(W\) のナップザックがある。次の条件を満たすように、アイテムを選んでナップザックに入れる。
選んだ品物の価値の合計をできるだけ高くする。
選んだ品物の重さの総和は \(W\) を超えない。
価値の合計の最大値を求めよ。
(具体例 1): ナップサックの容量を 40 のとき、次の品物のどれを選ぶべきか考えてみよう。
品物 |
価格 |
サイズ |
|---|---|---|
缶コーヒー |
120 |
10 |
ペットボトル水 |
130 |
12 |
バナナ |
80 |
7 |
りんご |
100 |
9 |
おにぎり |
250 |
21 |
パン |
185 |
16 |
(具体例 2): アルバイト可能な時間が 6 時間あるとすると、どのアルバイトを選べば最も稼げるだろうか？
アルバイト |
時給 |
稼働時間 |
|---|---|---|
データ入力 |
1250 |
5 |
プログラミング塾 |
1600 |
2 |
画像編集 |
1050 |
3 |
TA |
1300 |
2 |
Webサイト作成 |
1100 |
4 |
12.4.1. アプローチ1: ヒューリスティクス¶
多くの人は、価値の高いものから順番に入れていこうとするはずです。この方針は、ヒューリスティクスと呼ばれます。十分満足できる結果が得られることが多い一方、必ずしも最適解が得られることが保証されません。
[9]:
ITEMS = [
('缶コーヒー', 120, 10),
('ペットボトル水', 130, 12),
('バナナ', 80, 7),
('りんご', 100, 9),
('おにぎり', 250, 21),
('パン', 185, 16),
]
ITEMS.sort(key=lambda x: x[1], reverse=True) # 価値の高い順にソート
def max_value(W):
v = 0
w = 0
for item in ITEMS:
if w+item[2] <= W:
v += item[1]
w += item[2]
print(f'{item[0]}を選んだ')
return v, w
max_value(40)
おにぎりを選んだ
パンを選んだ
[9]:
(435, 37)
12.4.2. アプローチ2: 全探索¶
最適解を得るためには、アイテムひとつに対し、入れる/入れないの2通りの選択肢があります。 この組み合わせを全て調べて、最大値となる組み合わせを網羅的に選べばよいわけです。
深さ優先探索
[10]:
weight=0
value=0
def maxValue(W, i=0, w=0, v=0):
global weight, value
if i == len(ITEMS):
if w <= W and v > value:
value = v
weight = w
return v, w
# i番目のアイテムを選択
maxValue(W, i+1, w+ITEMS[i][2], v+ITEMS[i][1])
# i番目のアイテムを選択しない
maxValue(W, i+1, w, v)
return value, weight
maxValue(40)
[10]:
(470, 40)
この方針は、アイテム数が \(N\) のとき、\(2^N\) 通りの組み合わせを調べなければなりません。したがっ て、\(N\) が大きくなったとき、解を求めるのは難しくなります。
ナップサック問題
ナップサック問題は、NP 困難
実用的な逃げ道として、分岐限定法と呼ばれる方法があります。これは、枝刈りによって暫定解からその後の選択に含まれない経路を省略する手法です。
12.4.3. 動的計画法¶
ナップザック問題は、再帰構造が内在し、漸化式で書き直すことができます。これを活用して、最適解を求めることもできます。
まず、再帰構造を考えるため、問題をパラメータ化します。ポイントは、アイテムの数を増やす、最大容量を増やす、というように2つのパラメータを導入する点です。
ここでは、\(n( \le N )\) 個のアイテム、最大容量 \(w(< W )\) のときの最大価値を \(V (n, w)\) とします。すると、\(V (n, w)\) は漸化式で次のように表せます。
あとは、\(V (N, W )\) を計算することになります。落ち着いて取り組めば、動的計画法でも、メモ化再帰でも解が得られるようになります。