【個人メモ】超初心者的動的計画法～フィボナッチ数列～

初めに

静的な最適化で問題を解いていたが，扱うデータサイズが大きくなると計算が不可能になるので，動的計画法を導入したい．そのための勉強がてら．MATLABでやります．

動的計画法について

動的計画法については，他のサイトやQiita，書籍等で勉強し，まあ考え方は何となくわかったのだが，実装しようと思うとなかなか難しいと感じた．そのため，例題を解きながら習得しようというわけ．

フィボナッチ数列の実装

今回は最も簡単なところで，フィボナッチ数列の実装をしようと思う．

フィボナッチ数列の復習

高校の数学B？あたりで勉強したフィボナッチ数列．
(0),1,1,2,3,5,8,13,21,34,...
というやつ．
漸化式で書くと，

F_0=0\\
F_1=1\\
F_{n+2}=F_n+F_{n+1}(n\geq0)\\

となる．1個前と2個前の和．

素直に実装

フィボナッチ数列の漸化式に従って素直に実装すると以下の通り．

fibonacci_1.m

function fib = fibonacci_1(n)
if n <= 1
    fib = n;
else
    fib = fibonacci_1(n-2)+fibonacci_1(n-1);
end
end

とりあえず実装はできた．
後述するが，入力するnが大きくなると計算時間が爆発する．

動的計画法で解く

トップダウン（メモ化）

上記の素直な方法では，n番目を計算するためにn-1番目とn-2番目を計算する必要があり，そのn-1のためにn-2とn-3，n-2のためにn-3とn-4を計算して，...といった具合になるため，計算量が$2^n$の計算が必要になる．
そこで，トップダウン的な手法では，メモ化を用いて計算量を削減する．メモ化とは，結果を保持しておくことで，再計算を防ぐ手法のこと．ここでは，
MATLABにはメモ化のための関数(公式様のドキュメンテーション)がある．
この関数を使いつつ実装したのが以下．

fibonacci_2.m

function fib = fibonacci_2(n)
memoizedFcn = memoize(@fibonacci_2);
if n <= 1
    fib = n;
else
    fib = memoizedFcn(n-2)+memoizedFcn(n-1);
end
end

ググってもらうと他の言語でのフィボナッチ数列の実装例がたくさん出てくるが，このmemoize関数を使うとそれらに比べスマートにできる感じがする．まぁ，それらはわかりやすさのためにメモ化機能を使わないで実装しているだけだろうが．

ボトムアップ

最初の手法では，求めたいn番目の数値からnの小さい方へ向かって計算していくために計算量が多くなってしまう．
逆に，ボトムアップ的な手法では，1番目から順にn番目まで計算することで，余分な計算を回避する．手計算しようとしたら，自然とこの方法を取るだろうから，割と当たり前のような感じもするが．
実装上は，単純で，ループを用いて，1番目から順にn番目まで計算していくというもの．

fibonacci_3.m

function fib = fibonacci_3(n)
if n <= 2
    fib = 1;
else
    fib1=1;
    fib2=1;
    for i=1:n-2
        fib3=fib1+fib2;
        fib1=fib2;
        fib2=fib3;
    end
    fib=fib3;
end
end

パフォーマンス比較

動的計画法によってどの程度計算時間を短縮できたか比較してみる．

n=40;

tic
fibonacci_1(n);
elapsed_time_1 = toc

clearAllMemoizedCaches
tic
fibonacci_2(n);
elapsed_time_2 = toc

tic
fibonacci_3(n);
elapsed_time_3 = toc

n=40としたときの結果が以下．

1つ目の手法に比べ，それぞれ500分の1，2600分の1以下と，大幅に短縮された．

〆

wikiにもフィボナッチ数列の例は書いてありました．こちらを参考にして書いてます．
まあMATLABで実装したらってことで許してクレメンス...
今回は，トップダウンとボトムアップの手法の感じが掴めた感じ．
次回に続く...かも．