はじめに
動的計画法は非常に適応範囲の広い基本的なアルゴリズムです。ただ、最初はその仕組みや威力は理解しにくいものです。本記事ではフィボナッチ数列を例に動的計画法を用いて飛躍的に計算時間を短縮する方法を紹介ます。
動的計画法とは何か
検討しようとする難問をよりよく理解するために、多数の小部分に分割すること
——デカルト『方法序説』
動的計画法（以下DP）とは、対象となる問題を複数の部分問題に分割し、部分問題の計算結果の記録を利用して全体の問題を解く手法です。より具体的には以下の二点を満たすようなアルゴリズムを動的計画法と呼びます。
帰納的な関係の利用：小さな問題の計算結果を帰納的な関係を利用してより大きな問題を解く
計算結果の記録：小さな問題の計算結果を記録し、同じ計算を繰り返し行うことを避ける
DPの適応範囲は非常に広く、様々な種類のものがあります。今回扱うのは最もシンプルな例です。
フィボナッチ数列
フィボナッチ数列とは次の三項間漸化式によって非負整数項に対して定義される数列です。
\begin{align}
F_0 &= 0\\
F_1 &= 1\\
F_n &= F_{n-1} + F_{n-2}\,\,\,\,\,(n\geqq2)
\end{align}\tag{1}
DPを使わずにコードを書くとこのようになります。
def fibonacci(N):
if N <= 1:
return N
return fibonacci(N - 1) + fibonacci(N - 2)
非常に読みやすいコードですが、致命的な問題があります。例えばここで、print(fibonacci(10))として$F_{10}$を計算する場合を考えてみましょう。アルゴリズムのステップは次のようになります。
- $F_{10}$を求めるために$F_{9}$,$F_{8}$を呼び出し
- $F_{9}$,$F_{8}$を求めるために$F_{8}$,$F_{7}$,$F_{7}$,$F_{6}$を呼び出し
- $F_{8}$,$F_{7}$,$F_{7}$,$F_{6}$を求めるために$F_{7}$,$F_{6}$,$F_{6}$,$F_{5}$,$F_{6}$,$F_{5}$,$F_{5}$,$F_{4}$を呼び出し
- $F_{7}$,$F_{6}$,$F_{6}$,$F_{5}$,$F_{6}$,$F_{5}$,$F_{5}$,$F_{4}$を求めるために$F_{6}$,$F_{5}$,$F_{5}$,$F_{4}$,$F_{5}$,$F_{4}$,$F_{4}$,$F_{3}$,$F_{5}$,$F_{4}$,$F_{4}$,$F_{3}$,$F_{4}$,$F_{3}$,$F_{3}$,$F_{2}$を呼び出し
- $F_{6}$,$F_{5}$,$F_{5}$,$F_{4}$,$F_{5}$,$F_{4}$,$F_{4}$,$F_{3}$,$F_{5}$,$F_{4}$,$F_{4}$,$F_{3}$,$F_{4}$,$F_{3}$,$F_{3}$,$F_{2}$を求めるために$F_{5}$,$F_{4}$,$F_{4}$,$F_{3}$,$F_{4}$,$F_{3}$,$F_{3}$,$F_{2}$,$F_{4}$,$F_{3}$,$F_{3}$,$F_{2}$,$F_{3}$,$F_{2}$,$F_{2}$,$F_{1}$,$F_{4}$,$F_{3}$,$F_{3}$,$F_{2}$,$F_{3}$,$F_{2}$,$F_{2}$,$F_{1}$,$F_{3}$,$F_{2}$,$F_{2}$,$F_{1}$,$F_{2}$,$F_{1}$,$F_{1}$,$F_{0}$を呼び出し
終わりまで書かなくてもお気づきかと思います。重複して、つまり無駄に呼び出している項が沢山あります。呼び出しの深さはおよそ$N$で、呼び出す項の数は深くなるたび倍々に増えます。このアルゴリズムの計算時間は$O(2^N)$となってしまいます。これは絶望的な数字で、$N$が大きくなれば手計算よりはるかに時間がかかってしまいます。
具体的にどれほどのことなのか見積もってみましょう。例えば、手計算では、$1$秒に$1$回程度の足し算ができ、$N$までの項をそれぞれ一度しか計算しないと仮定してみましょう。フィボナッチ数列の第$100$項目を求めるためにかかる時間はおよそ$2$分です。
対するコンピュータが$1$秒で$10$億回の計算ができると仮定したうえで、このアルゴリズムを使って$F_{100}$を導くのにかかる時間を見積もりましょう。$2^{100}=1267650600228229401496703205376$なので、およそ$40196936841331474432000$年（$400$垓年）かかります。これは、まったくもって現実的な数字ではありません。
一応もう少しマシな想定も個人的に考えてみました。コンピュータに勝機はあるでしょうか。この悪いアルゴリズムでは$F_{N}$を求めるために$F_{N-1}$と$F_{N-2}$を再起呼び出ししていました。つまり、$F_{N}$の計算時間はおよそ、$F_{N-1}$の計算時間と$F_{N-2}$の計算時間の和であると考えられます。そうすると、計算時間の増加量そのものもフィボナッチ数列になっていると考えられます。特性方程式$X^2=X+1$を用いてフィボナッチ数列の一般項を導くと、
$$
F_{N} = \frac{1}{\sqrt{5}}\bigg\lbrace{\bigg(\frac{1+\sqrt{5}}{2}\bigg)}^N-{\bigg(\frac{1-\sqrt{5}}{2}\bigg)}^N\bigg\rbrace\tag{2}
$$
となりますので、十分大きな$N$に対して隣接項の比は、
$$
\lim_{N \to \infty} \frac{F_{N+1}}{F_{N}}=\frac{1+\sqrt{5}}{2}\tag{3}
$$
となります。この比は黄金比と呼ばれ、およそ$1.618$程度です。計算時間も黄金比を$\varphi$として$\varphi^N$程度となると仮定したらどうでしょうか。この場合計算時間は$792070839848374894592$秒となり、約$25$兆年で済みそうです。
import numpy as np
golden_ratio = (1 + np.sqrt(5)) / 2
ran_time = golden_ratio ** 100
print(ran_time)
print(ran_time/(60*60*24*365))
ではDPを使うとどうなるでしょうか。DPを使うとこの無駄な呼び出しがなくなって、計算時間が$O(N)$となります。コードは次のようになります。
def fibonacci_dp(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]
このコードでは、関数fibonacci_dpは再起呼び出しを行っていません。上からコードを見ていきましょう。
def fibonacci_dp(N):
if N <= 1:
return N
この部分は最初のコードと同じです。定義より、入力が0または1の時はそのまま返します。
ここから、DPの準備をします。
dp = [0] * (N + 1)
dp[1] = 1
一行目では、長さ$N+1$の配列dpを宣言し、その各項に値$0$を代入しています。この配列dpには最終的に第$0$項から第$N$項までのフィボナッチ数列を格納します。
二行目ではdp[1]=1として第一項に値$1$を代入しています。これは必要な初期条件です。これから初期条件として実際に値を使うのは$0$が格納されたdp[0]と$1$が格納されたdp[1]のみです。
for i in range(2, N + 1):
dp[i] = dp[i - 1] + dp[i - 2]
ここでは第$2$項以降のフィボナッチ数列を目的に第$N$項まで計算しています。途中の計算結果はすべて配列dpに記録されているので手戻りしたり、同じ計算を複数の処理から呼び出すようなことはありません。この操作がそもそもDPなのかどうなのかというのは最初分かりにくいですが、紹介したDPの定義帰納的な関係の利用と計算結果の記録を確かにこのコードでは行っているのです。
最後にこの威力を体感するために実行時間を計測してみましょう。実行時間計測にはtimeモジュールをimportします。
import time
def fibonacci_dp(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]
start_time = time.time()
print(fibonacci_dp(100))
end_time = time.time()
print(end_time - start_time)
出力は下のようになりました。
354224848179261915075
0.00016808509826660156
一行目が解答で、二行目が実行時間（秒）です。下手をすると$400$垓年掛かりそうだった$F_{100}$の計算をDPを活用することで、$0.000168$秒で完了してしまいました。
補足：再起呼び出しの制限について
深い再起呼び出しを行おうとすると、通常のPython環境では呼び出し回数制限にあいます。これはコードが無限ループに陥っているときにループを強制的に終了するための仕様ですが、sysをimportすることで以下のようなコードで呼び出し回数上限を設定することができます。
import sys
# デフォルトの再帰深さ制限を確認
print(sys.getrecursionlimit())
# 再帰深さ制限を100000000に変更
sys.setrecursionlimit(10 ** 8)
# 設定したの再帰深さ制限を確認
print(sys.getrecursionlimit())