フィボナッチ数列で動的計画法を学ぶ

競技プログラミングを始めて、DP(動的計画法：Dynamic Programming)という言葉を何度か目にするようになりました。動的計画法について全く知らなかったので、今回はフィボナッチ数列を例に、動的計画法について勉強をしました。

def fibonacci_refunc(n):  
    if (n==1 or n==2):return 1
    return fibonacci_refunc(n-1)+fibonacci_refunc(n-2)
print(fibonacci_refunc(4)

これは愚直にフィボナッチ数列の定義式をそのまま書いたものとなっています。 例のコードは$F_4$を求めるコードとなっています。このコードを簡単に解説しますと、n=1か2となるまで、自分自身を呼び出します。今回の例では、$F_4$を求めるのに$F_3、F_2$が必要となります。$F_2$は1を返して終了するのでいいのですが、$F_3$を求めるのにはもう一度自分自身を呼び出して$F_2$と$F_1$を求めなければいけません。

言葉では少し分かりずらいので、図にすると次のようになります。

図1:4番目のフィボナッチ数を再帰関数で求めた場合

図1を見ていただくと分かる通り、$F_4$を計算するにあたり、$F_2$を2回計算する必要があります。今回はn=4なので、同じ計算は2回しかしないですが、nが増えるにしたがって、同じ計算を何度もしなければいけないので、非常に効率が悪い計算となってしまいます。

動的計画法を用いた場合

具体的には次のようになります。

def fibonacci_dp(n):
    F = [1,1]
    for i in range(1,n-1):
        F.append(F[i]+F[i-1])
    return F[-1]
print(fibonacci_dp(4))

上記のコードはフィボナッチ数がちゃんと計算できているかを確認するために、フィボナッチ数列をどんどん配列に格納していっています。
もし、$F_n$の値一つだけを知りたい場合は下記のようにすることで、メモリを節約することが出来ます。

def fibonacci_dp2(n):
    if n == 1 or n==2:
        return 1 
    else:
        fib1 = 1
        fib2 = 1
        for i in range(n-2):
            fib3 = fib1+fib2
            fib1 = fib2
            fib2 = fib3
        return fib2
print(fibonacci_dp(4))

再帰関数、動的計画法の比較

比較するにあたって用いたコードは下記の通りです。それぞれの方法で$F_1$から$F_{40}$まで求めています。

import time
import timeit
import matplotlib.pyplot as plt
import seaborn
def fibonacci_refunc(n):
    if (n==1 or n==2):return 1
    return fibonacci_refunc(n-1)+fibonacci_refunc(n-2)

def fibonacci_dp(n):
    F = [1,1]
    for i in range(1,n-1):
        F.append(F[i]+F[i-1])
    return F[-1]


time_refunc = []
time_dp = []
fibonacci_dp_list = []
fibonacci_refunc_list = []
for i in range(1,41):
    total_time_dp = timeit.timeit("fibonacci_dp(i)",globals=globals(),number=1)
    total_time_refunc =  timeit.timeit("fibonacci_refunc(i)",globals=globals(),number=1)
    time_refunc.append(total_time_refunc)
    time_dp.append(total_time_dp)
    fibonacci_dp_list.append(fibonacci_dp(i))
    fibonacci_refunc_list.append(fibonacci_refunc(i))

x_axis = range(1,41)
print(fibonacci_dp_list)
print(fibonacci_refunc_list)
print(time_dp)
print(time_refunc)

plt.plot(x_axis,time_dp)
plt.plot(x_axis,time_refunc)
plt.show()

計算結果を確認すると次のようになりました。

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155]



[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155]

少し見ずらくて申し訳ないのですが、上が動的計画法で求めたフィボナッチ数列、下が再帰関数を用いて求めたフィボナッチ数列となっています。2つで同じ計算が出来ていることが分かります。

次に計算時間について見てみます。

[2.4683182536718875e-06, 1.4104675735268006e-06, 2.4683182536718875e-06, 2.115701360290228e-06, 1.7630844669085143e-06, 2.1157013602901738e-06, 2.4683182536718333e-06, 2.4683182536719417e-06, 2.468318253671725e-06, 2.8209351470537096e-06, 3.5261689338170286e-06, 3.1735520404354775e-06, 3.5261689338170286e-06, 3.5261689338172454e-06, 3.5261689338168117e-06, 3.878785827199013e-06, 3.878785827199013e-06, 4.2314027205803476e-06, 3.878785827199013e-06, 4.23140272057948e-06, 4.231402720581215e-06, 4.23140272057948e-06, 5.994487187490488e-06, 8.815422334537693e-06, 8.815422334537693e-06, 1.692561088231792e-05, 1.2341591268394403e-05, 8.462805441145083e-06, 8.81542233455157e-06, 1.3752058841909331e-05, 8.81542233455157e-06, 1.057850680163952e-05, 1.1988974375043426e-05, 1.4104675734927241e-05, 9.520656121253523e-06, 1.868869534860096e-05, 1.128374058723125e-05, 1.1988974371490713e-05, 1.304682504610355e-05, 1.7630844695304404e-05]



[1.0578506801451004e-06, 7.052337867634003e-07, 1.76308446690846e-06, 1.4104675735267464e-06, 2.1157013602901738e-06, 3.1735520404352607e-06, 4.936636507343775e-06, 7.75757165439716e-06, 1.1988974374977724e-05, 1.8336078455848245e-05, 2.92672021506811e-05, 4.6898046819766025e-05, 7.475478139691983e-05, 0.00012094759442992254, 0.00019499714204007906, 0.00031664997025676513, 0.0005116471122968442, 0.0008134871730315777, 0.001187261080016178, 0.0019161201986361495, 0.003096328940784694, 0.005029374750303163, 0.01153339334872859, 0.02005226487593703, 0.03254266047330355, 0.07955848133545892, 0.06520908947618409, 0.09062606776803034, 0.1593669680483255, 0.35882788734172344, 0.5738180546196519, 0.8188998423449867, 1.316810763560147, 2.1742854835735184, 3.5077542217939115, 6.389558096983045, 10.019768408276764, 15.695785064488348, 24.625684120850266, 40.158886351222634]

こちらも見ずらくて申し訳ありません。上の配列が動的計画法で求めた場合の計算時間で、下の配列が再帰関数を用いた場合の計算時間となっています。

動的計画法の場合nが増えても計算時間の変化は少ないですが、再帰関数を用いた場合はnが増加すると一気に計算時間が増加してしまうことが分かります。

これだと分かりずらいので、グラフにしたものを以下に示します。

図2は横軸がnの値で、縦軸が計算時間となっています。また、緑線が再帰関数を用いた場合で、青線が動的計画法を用いた場合です。
図2を見て頂くと、再帰関数を用いた場合は指数関数的に計算時間が増加していることが分かります。

まとめ

参考文献