動的計画法とは？意味をやさしく解説 - サードペディア百科事典

動的計画法（Dynamic Programming）とは

動的計画法（DP）は、計算機科学におけるアルゴリズム設計手法の一つです。与えられた問題を、より小さな部分問題に分割し、それらの解を記録・再利用することで、効率的に問題を解決します。この手法は、特に最適化問題や組み合わせ問題を解く際に強力な威力を発揮します。

動的計画法の定義

動的計画法は、特定のアルゴリズムを指すのではなく、以下の2つの条件を満たすアルゴリズムの総称です。

1. 帰納的な関係の利用: より小さな部分問題の解や計算結果を用いて、より大きな問題の解を導き出す。
2. 計算結果の記録: 一度計算した結果を記録し、同じ計算を繰り返すことを避ける（メモ化）。

動的計画法の概要

動的計画法の概念は、1940年代にリチャード・E・ベルマンによって提唱され、1953年に現在の定義が確立されました。問題を帰納的に解く際に、同じ部分問題が繰り返し出現する場合に、その結果を表に記録し、冗長な計算を省くことで効率化を図ります。

動的計画法は、単純な問題ではフィボナッチ数列の計算やハノイの塔の移動回数の計算などで、指数関数的な計算時間を線形時間へと短縮することができます。特に、文字列の近似照合（編集距離の計算）やナップサック問題といった組み合わせ問題において、二次元の表を用いることで指数時間の手続きを多項式時間に効率化できることは、動的計画法の大きな特徴です。

ただし、テーブルの次元数が増加すると、メモリ使用量が大きくなり、実用性が低下することがあります。

近似アルゴリズムの分野では、動的計画法を適用することで、一部の問題において疑似多項式時間で最適解を得ることができます。

動的計画法の実現方法

動的計画法には、主に以下の2つの実現方法があります。

1. トップダウン方式（メモ化再帰）: 分割統治法を基に、計算結果をメモ化して再利用します。再帰呼び出しを伴う場合によく用いられます。
2. ボトムアップ方式: より小さい部分問題から順に解いていき、その結果を組み合わせて全体の問題を解決します。

動的計画法の適用条件

最適化問題に動的計画法を適用する場合、以下の2つの条件が成立している必要があります。

1. 部分構造最適性: 問題の最適解が、部分問題の最適解によって構成される。
2. 部分問題重複性: 同じ部分問題が繰り返し現れる。

部分構造最適性は、部分問題も同じ最適化問題を解くものであり、各部分問題が独立していることを意味します。たとえば、最短経路問題では、ある経路が最短であるとき、その部分経路もまた最短である必要があります。

部分問題重複性は、計算結果を再利用することで効率化を図るために重要です。

動的計画法の例

動的計画法の適用例として、フィボナッチ数列の計算を例に説明します。

フィボナッチ数列

フィボナッチ数列は、各項が前の2つの項の和となる数列です。

定義を直接実装したプログラム

再帰的な定義に基づいた実装は以下のようになります。

python
def fib(n):
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)

この実装では、同じ部分問題が何度も計算され、計算時間が指数関数的に増加します。

動的計画法を利用したプログラム（ボトムアップ方式）

python
def fib_dp_bottom_up(n):
if n <= 1:
return n
dp = [0] (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]

ボトムアップ方式では、部分問題の解を順に計算し、再利用することで、計算時間を線形時間まで短縮できます。

動的計画法を利用したプログラム（トップダウン方式）

python
def fib_dp_top_down(n, memo):
if n <= 1:
return n
if memo[n] != -1:
return memo[n]
memo[n] = fib_dp_top_down(n-1, memo) + fib_dp_top_down(n-2, memo)
return memo[n]

def fib_memo(n):
memo = [-1] (n + 1)
return fib_dp_top_down(n, memo)

トップダウン方式では、再帰呼び出しとメモ化を組み合わせることで、効率的に問題を解決します。

まとめ

動的計画法は、問題を部分問題に分割し、その結果を再利用することで効率的に解く手法です。特に、最適化問題や組み合わせ問題において有効であり、計算時間の短縮に大きく貢献します。トップダウン方式とボトムアップ方式のどちらを選択するかは、問題の性質によって判断することが重要です。

動的計画法