📂アルゴリズム

ダイナミックプログラミング

ビルドアップ

問題を解く時、大きな問題の解答がそれより小さい問題の解答を含んでいれば、最適部分構造^{optimal Substructure}を持つと言われる。最適部分構造を持つ問題の例として一番簡単なのが フィボナッチ数を求めることである。$n$ 番目のフィボナッチ数は$a_{n} = a_{n-1} + a_{n-2}$ のように求められるため、大きな問題 $a_{n}$ が小さな問題 $a_{n-1}$、$a_{n-2}$ を含んでいるからである。

これを簡単に解く方法は、再帰関数を使うことである。実際、最適部分構造を持っていればどんな問題も再帰関数で解けそうだが、実装してみると、重複呼び出しのために非常に非効率的である。

定義

動的プログラミング^{dynamic Programming}は、これらの困難を回避するための技術であり、次の条件を満たす時に使ってみる価値がある：

• (i): 与えられた問題が最適部分構造を持っている。
• (ii): 再帰関数で実装するには非効率的である。

例

動的プログラミングの概念は単純だ。小さな問題の解答を保存しながら、重複呼び出しを省略することである。たとえば、6番目のフィボナッチ数$a_{6}$を求めるためには $$ a_{1} = 1 \\ a_{2} = 1 \\ a_{3} = 2 \\ a_{4} = 3 \\ a_{5} = 5 $$ を何度も計算するのではなく、メモリに保存しておき、最後に$a_{4}$と$a_{5}$だけを呼び出して$a_{6} = a_{5} + a_{4} = 8$を計算する。これをメモイゼーション^memoizationと言う¹。

説明を読めば、特にダイナミックではないように思えるが、元々は制御分野で、解答をテーブルに保存しながら解いていくことから由来した言葉だという説があった。しかし、動的プログラミングの考案者であるベルマン^bellmanが自著で明かしたところによると、ダイナミックという言葉が格好良く、資金獲得に適しているから選んだとのことである。

以下は、$a_{36}=14930352$を二つの方法で計算し、その時間を計測したGIFと、そのPythonコードである。動的プログラミングでは0.01秒ちょっとの時間しかかからなかったが、再帰関数では5秒以上かかった。この差は$n$が大きくなるほど大きくなる。理論的にも、与えられた$n$に対して再帰関数は指数的に、動的プログラミングは線形に時間を使うことが簡単に証明できる。

コード

import Time

def fibo1(n) :
    if n==1 or n==2 :
        return 1
    else :
        return fibo1(n-1) + fibo1(n-2)

def fibo2(n) :
    memoization = [1,1]
    for i in range(n-2) :
        memoization.append(memoization[-1]+memoization[-2])
    return memoization[-1]

start = Time.time() 
print(fibo2(36))
print("동적 프로그래밍으로 계산할 때 걸린 시간 : %5.3f" % (time.time() - start))

start = Time.time() 
print(fibo1(36))
print("재귀함수로 계산할 때 걸린 시간 : %5.3f" % (time.time() - start))