python アルゴリズム プログラミング

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

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

フィボナッチ数列について

wikipedia (フィボナッチ数）によるとフィボナッチ数列は以下のように定義されています。
\begin{equation}F_0 = 0 , F_1 = 1 \\ \nonumber
F_{n+2} = F_n + F_{n+1} \end{equation}

これを具体的に書くと0,1,1,2,3,5,8,13,21,34 ...と続いていきます。
色々な記事を見ていると、フィボナッチ数列は$F_0$、すなわち0を無視して、$F_1$からスタートしている例が多い気がします。

フィボナッチ数列を求めるプログラム

再帰関数を用いた場合

言語はpythonです。

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を見て頂くと、再帰関数を用いた場合は指数関数的に計算時間が増加していることが分かります。

まとめ

今回はフィボナッチ数列を例に動的計画法について学びました。動的計画法を用いることで、同じ計算を何度も繰り返す必要がなくなるので、計算時間の短縮につながるということが分かりました。

フィボナッチ数列の場合は一次元配列で実装できるため、簡単でしたが、ナップサック問題のように2次元配列で実装する必要がある場合についても勉強していきたいです。

参考文献



0 件のコメント :

コメントを投稿