5.1 動的プログラミングの定義。
動的プログラミング (Dynamic Programming, DP) は、複雑な問題をより簡単なサブ問題に分割して解決する最適化の手法だよ。動的プログラミングは 最適なサブ問題の構造を持つ、重なるサブ問題を持つ問題に対して効果的だよ。
動作の原則:
1. 最適な下部構造:
問題が最適な下部構造を持っている場合、その最適解はサブ問題の最適解から構築できるよ。つまり、いくつかの小さなサブ問題を解決することで大きな問題を解決できるってこと。
2. 重なるサブ問題:
問題が重なるサブ問題を持っている場合、それらのサブ問題は問題の解決過程で何度も繰り返されるよ。動的プログラミングは、既に解決済みのサブ問題の結果を記憶して（メモ化）重なるサブ問題を効率的に解決するよ。
3. メモ化とタブレーション:
メモ化（トップダウン）: 再帰的なアプローチで、サブ問題の結果をメモリに保存して再計算を避ける。
タブレーション（ボトムアップ）: イテラティブなアプローチで、サブ問題の結果をテーブル（通常は配列）に計算して保存し、最終結果の計算に使う。
動的プログラミングで解決される問題の例
5.2 ナップサック問題。
問題:
重さと価値のあるアイテムのセットがあるよ。ナップサックの容量制限を守りつつ、全体の価値を最大化するためにアイテムを選んでね。
重要! 貪欲アルゴリズムで簡単に解決できる類似問題とは違って、この問題ではアイテムを分割することはできないよ。
解決法:
アイテムに対応する行と、ナップサックの可能な容量に対応する列を持つテーブルを作るよ。セルの値は、そのアイテムの数と容量に対する最大価値を表すよ。
時間計算量: O(n * W)、ここでnはアイテムの数、Wはナップサックの容量だよ。
Pythonのコード例:
def knapsack(weights, values, W):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
if weights[i - 1] <= w:
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]
5.3 最短経路問題
問題:
重み付きグラフのすべての頂点のペア間の最短経路を見つける。
解決法:
行と列がグラフの頂点に対応するテーブルを使うよ。セルの値は二つの頂点間の最短距離を表すよ。
時間計算量: O(V^3)、ここでVは頂点の数だよ。
Pythonのコード例:
def floyd_warshall(graph):
v = len(graph)
dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
for k in range(v):
for i in range(v):
for j in range(v):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
5.4 動的プログラミングと他の方法の比較。
ブートフォース（brute force）法との比較:
時間計算量:
-
ブートフォース: よく指数的な時間計算量を持ってる (たとえば、
O(2^n)フィボナッチ問題の場合)。 -
動的プログラミング: 時間計算量を多項式時間に減らす (たとえば、
O(n)フィボナッチ問題の場合)。
空間計算量:
- ブートフォース: メモリ使用量は少ないことがあるが、時間のコストが高い。
-
動的プログラミング: 中間結果を保存するためにより多くのメモリを使用することがある (たとえば、
O(n)メモ化されたフィボナッチ問題の場合) が、時間で有利だよ。
グリーディーアルゴリズム（greedy algorithms）との比較:
最適性:
- グリーディーアルゴリズム: 常にグローバルな最適解を見つけるとは限らないが、より早く、実装が簡単だよ。
- 動的プログラミング: グローバルな最適解を見つけるけど、計算資源を多く必要とする。
問題の例:
- グリーディーアルゴリズム: 分数ナップサック問題、最小全域木 (MST)。
- 動的プログラミング: ナップサック問題（整数）、最長共通部分列 (LCS)。
GO TO FULL VERSION