動的計画法
はじめに
動的計画法(Dynamic Programming)は、問題をより小さな部分問題に分割して解く効率的なアルゴリズム設計手法です。 部分問題の結果を保存しておくことで、無駄な再計算を避けます。
この手法を広めたのはリチャード・ベルマンです(そう、Bellman-Ford法のベルマンと同じ人物です)。
例:フィボナッチ数
フィボナッチ数
フィボナッチ数列は、各項が直前の2つの項の和になっている数列です。 例: 1, 1, 2, 3, 5, 8, 13, 21 …
フィボナッチ数の素朴な再帰アルゴリズム
F(n)を求める単純な再帰の解法です:
def fib_naive(n):
if n <= 2:
return 1
else:
return fib_naive(n - 1) + fib_naive(n - 2)ただしこれは悪い解法です。計算量はO(2ⁿ)、つまり指数時間になります。 関数が何回呼ばれるか数えてみましょう:
cnt = 0
def fib_naive(n):
global cnt
cnt += 1
if n <= 2:
return 1
else:
return fib_naive(n - 1) + fib_naive(n - 2)
print(fib_naive(20))
print("OMG. Function was called", cnt, "times.")メモ化アルゴリズム
「memorized(暗記した)」ではなく、**memoized(メモ化した)**アルゴリズムです 😄 このバージョンでは、各結果を辞書に保存します。同じ値を再び計算しようとしたときは、保存済みの結果をそのまま返します。
def fib_memo(n, memo=None):
if memo is None: memo = {} # ①
if n in memo: return memo[n] # ②
if n <= 2: result = 1 # ③
else: result = fib_memo(n - 1, memo) + fib_memo(n - 2, memo) # ④
memo[n] = result # ⑤
return result解説:
① 最初の呼び出しで空の辞書を作ります。
② すでにこのnを計算済みなら、それを返します。
③ ベースケース: F(1)とF(2)はどちらも1です。
④ 素朴版と同じロジックですが、メモ化を加えています。
⑤ 次回の再計算を避けるため、結果を保存します。
このバージョンが何回実行されるか数えてみましょう:
cnt = 0
def fib_memo(n, memo=None):
global cnt
cnt += 1
if memo is None: memo = {}
if n in memo: return memo[n]
if n <= 2: result = 1
else: result = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
memo[n] = result
return result
print(fib_memo(20))
print("Yep. Function was called only", cnt, "times.")計算量はO(n)、空間計算量もメモ用の辞書と再帰スタックのため**O(n)**です。
ボトムアップDP | 時間: O(n)、空間: O(1)
メモ化版も効率的ですが、さらに改善できます。 メモ化版と素朴版はどちらもトップダウンで計算しますが、人間はふつうボトムアップ、つまり土台から順に考えます。
ボトムアップDPなら、直前の2つの値だけを保持することで空間も**O(1)**に削減できます。
def fib_bottom_up_O1(n):
if n <= 2: return 1
prev, curr = 1, 1
for k in range(2, n):
prev, curr = curr, prev + curr
return curr- 2から
nまで反復します prevとcurrの2変数だけを使います- とても高速でメモリ効率も良いです
ボトムアップDP | 時間: O(n)、空間: O(n)
O(1)版はF(n)だけが必要なら最適です。 しかし、nまでのフィボナッチ数列全体が欲しい場合はどうでしょう?
def fib_bottom_up_On(n):
if n == 1: return [1]
if n == 2: return [1, 1]
fib = [0] * n
fib[0], fib[1] = 1, 1
for k in range(2, n):
fib[k] = fib[k - 1] + fib[k - 2]
return fibここでは全ての値を配列に保存するので、空間は**O(n)**になります。
2次元DPテーブル(タビュレーション) | 時間: O(m × n)、空間: O(m × n)
2つの入力(例えば2つの文字列)を扱う問題では、部分問題の解を保存するために2次元DPテーブルをよく使います。各セルdp[i][j]は、text1の先頭i文字とtext2の先頭j文字に対する解を保存します。
典型例は最長共通部分列(LCS)です:
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
# Create a (m+1) x (n+1) DP table initialized with 0
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Build the table from top-left to bottom-right
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1] # characters match
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # carry forward the max
return dp[m][n] # bottom-right cell has the final result- dp[i][j]の意味: text1[:i]とtext2[:j]のLCSの長さ
- ベースケース(i == 0 または j == 0)を扱うため、行と列を1つずつ余分に取って初期化します
- 文字が一致すれば、斜めに進みます
- 一致しなければ、左または上の最良の結果を採用します
可視化:
"" a c b e
"" 0 0 0 0 0
a 0 1 1 1 1
b 0 1 1 2 2
c 0 1 2 2 2この手法はとても強力で、次のような問題にも拡張できます:
- 編集距離(Edit Distance)
- ナップサック問題
- 回文部分文字列
まとめ
動的計画法は、特に次の性質を持つ問題を効率的に解くための強力な手法です:
- 部分問題の重複(Overlapping subproblems)
- 最適部分構造(Optimal substructure)
実装方法はいくつもあります:
- 素朴な再帰(遅い)
- メモ化によるトップダウン(高速で読みやすい)
- ボトムアップ(より高速で省メモリ)
- ボトムアップ最適化(空間O(1)!)
- 2次元DPテーブル(タビュレーション)(2入力に強力)
何が欲しいかによって選び方は変わります: 最終結果だけ? すべての中間値? 自分のケースに合った手法を選びましょう。
さらに高度な応用もあります:
- グラフの最短経路(ダイクストラ法、ベルマンフォード法など)
- ナップサック問題
- 編集距離
- ゲーム理論 など
現実の問題にはどう応用できる?
- 地図上の最短経路の計算(例: Google Maps、ナビゲーション)
- 株の利益最適化、予算配分、スケジューリング
- 予測変換アルゴリズム(例: スペル訂正のための編集距離)
- ゲームAI — 最適な手の探索
- DNA配列のアラインメント
- 画像圧縮
- テキストの分割
他の手法との比較は?
| 手法 | 時間 | 空間 | 備考 |
|---|---|---|---|
| 素朴な再帰 | O(2ⁿ) | O(n) | 書きやすいが非常に遅い |
| メモ化 | O(n) | O(n) | 高速・読みやすい・再帰的 |
| ボトムアップ(タビュレーション) | O(n) | O(n) | より高速・反復的 |
| ボトムアップ最適化 | O(n) | O(1) | 最速・最小メモリ |
| 2次元DPテーブル(タビュレーション) | O(m × n) | O(m × n) | 2入力に強力 |
DPを使わない方がよいのはどんなとき?
- 問題に部分問題の重複がないとき
- 貪欲法や分割統治法の方が単純で高速なとき
- 制約が十分に小さく、全探索で間に合うとき
参考
動的計画法の概要は、このすばらしいMITの講義(YouTube)で学びました。 こうした素晴らしいコンテンツを無料で公開しているMITに感謝します。
YouTube: Lecture 19 — Dynamic Programming I: Fibonacci, Shortest Paths