動的計画法０ フィボナッチ数
つくばチャレンジ本番まであとわずかですが，，，カメラとLidarのフュージョンをするにあたってせっかくなのでSGMとStixelをちゃんと理解しておこうと思い論文を読んでます．
SGMの論文
https://core.ac.uk/download/pdf/11134866.pdf
Stixelの論文
http://www.lelaps.de/papers/badino_dagm09.pdf
が，，，SGMもStixelも動的計画法がキーなんですが，これがいまいち理解できず．．．このあたり，やっぱり情報系の基礎・基本がなってないんだろうなあと思います．ということで，遠回りではあるんですが，一念発起して今週は動的計画法の勉強をすることにしました．
動的計画法の定義
で，積読してあったアルゴリズムの本を開いて定義から確認です．動的計画法は英語では Dynamic Programming というそうですが，この Programming という単語はプログラミングの意ではなく，【表】を意味するんだそうです．ということで，厳密な意味で言うと動的計画法は
"計算結果を表に保存しておき，必要になったらその結果を利用することで計算の効率化を図る方法．"
といえるのかなと思います．動的計画法のキモは，”【表】をどうやって作るか？”というところかなと理解しました．この定義だけ書いても意味不明だと思うので，最初の例題としてフィボナッチ数列をやってみます．
フィボナッチ数列
フィボナッチ数列はググればいろんな情報が出てきます．ひとまず，Wikipediaのリンクを載せておきます．
フィボナッチ数 - Wikipedia
で，実際のフィボナッチ数列の定義ですが，下記のようになります．
こいつをプログラムで求めるとすると，下記のようになります．
def fibonacci_recursive(n):
print("fibonacci(" + str(n) + ")")
if (n == 0):
return 0
elif (n == 1):
return 1
return fibonacci_recursive(n-2) + fibonacci_recursive(n-1) この再帰関数は，nが0か1になるまでスタックに関数が積まれていきます．試しにn=6として上記関数を実行すると，下記のように関数がコールされます．
fibonacci(6), fibonacci(4), fibonacci(2), fibonacci(0), fibonacci(1), fibonacci(3), fibonacci(1), fibonacci(2), fibonacci(0), fibonacci(1), fibonacci(5), fibonacci(3), fibonacci(1), fibonacci(2), fibonacci(0), fibonacci(1), fibonacci(4), fibonacci(2), fibonacci(0), fibonacci(1),
fibonacci(3), fibonacci(1), fibonacci(2), fibonacci(0), fibonacci(1)
たかだかフィボナッチ数列の6項目を求めるのために，かなりの回数関数が呼ばれていることがわかります．ひとつの関数が2つの関数を再帰的に呼び出すので，図にすると下記のように2分木になります．
で，上図を見てもらうとわかるんですが，一度計算している関数が何回も呼ばれていることがわかります．例えば，fib(4)とか．一度計算した値に関しては保存しておいて再利用すれば，関数を呼び出す回数はかなり削減できそうです．
メモ化再帰を用いたフィボナッチ数列の計算
ということで，一度計算済のフィボナッチ数をメモしながらフィボナッチ数を求めます．
def fibonacci_recurcive_memo(n):
memo = np.zeros(n+1)
memo.fill(-1)
return fibonacci_recurcive_memo_int(n, memo)
def fibonacci_recurcive_memo_int(n, memo):
print("fibonacci(" + str(n) + ")")
if (memo[n] != -1):
return memo[n]
elif (n == 0):
memo[n] = 0
return memo[n]
elif (n == 1):
memo[n] = 1
return memo[n]
else:
memo[n-2] = fibonacci_recurcive_memo_int(n-2, memo)
memo[n-1] = fibonacci_recurcive_memo_int(n-1, memo)
return memo[n-2] + memo[n-1]同じようにn=6として実行すると，下記のように関数が呼ばれていきます．
fibonacci(6), fibonacci(4), fibonacci(2), fibonacci(0), fibonacci(1), fibonacci(3), fibonacci(1), fibonacci(2), fibonacci(5), fibonacci(3), fibonacci(4)
一度計算した値を保存して再利用することで，関数の呼び出し回数がかなり減りました．再帰呼出しの中で途中結果を保存しておく方法を"メモ化再帰"と呼ぶようです．おそらく厳密な意味ではこれは動的計画法ではなく，”分割統治法・再帰法+メモ化再帰”なのだと思います．ただ，メモ化再帰ができるということは，表（＝メモ）を作ることができます．
動的計画法を用いたフィボナッチ数列の計算
やっとこさ本題の動的計画法です．最初に説明したように，動的計画法で問題を解くには，”表”を作る必要があります．この問題の場合は，fib(0), fib(1), fib(2), ...というようにそれぞれのフィボナッチ数を表として作成する必要があります．で，ここでポイントなんですが，フィボナッチ数を求める際に，値が定義されているのは n=0とn=1だけです．あとは漸化式を解いて求める必要があります．つまり，表を計算するときにも，nが小さい方から計算していく必要があります．動的計画法（＝表作成）は，この例のようにボトムから解ける問題に対して応用可能な技法になります．基本的には，問題を漸化式の形に落とし込めることができれば，動的計画法で問題が解ける可能性が大ということかと思います．
