どうてきけいかくほう

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

ダイナミックプランニングは、複雑な問題を複数の単純な問題に分解する方法です.これは,従来の方法よりも少ない時間で局所問題の繰返しと最適局所構造を解くためのアルゴリズムである.
ダイナミックプランニングは、複数のサブ問題を解き、結果を記録し、それらを使用して問題を解決するアルゴリズムです.すなわち,再帰関数を解放する際に用いられる関数を定式化するだけでよい.問題をF(string)=F(string[1:n-2])として定義できるように分割定義できる場合は、動的プランニング法を使用します.
これは再帰アルゴリズムと非常に似ているが,結果を記録して使用するのとは異なる.
記録結果を「注釈化」(Memoization)と呼び,分解可能な問題の構造を「オーバーラップ部分問題」(Overlapping Subproblem)と呼ぶ.
1つの典型的な例はフィボナッチ数列であり,再帰と動的計画法の違いを見ることができる.再帰関数を用いてフィボナッチ数列を行うだけでは,100番目の数列値を得るには演算が非常に多くなり,長い時間がかかる.しかし、記録して検索して書き込むと、演算量を大幅に減らすことができます.
再帰関数を使用したフィボナッチ

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

境遇
n=4面fibo(3)、dibo(2)を受け入れると、fibo(3)はfibo(2)とfib 0(1)という演算を繰り返します.
ダイナミックプランニング法を用いたフィボナッチ

def fibo_recursion(n, fibo_memo):
    if n in fibo_memo:
        return fibo_memo[n]

    nth_fibo = fibo_recursion(n-1, fibo_memo) + fibo_recursion(n-2, fibo_memo)
    fibo_memo[n] = nth_fibo
    return nth_fibo

この場合、fibo memoディレクトリに値が格納されて演算されます.
操作した場合は、レコードの値を読み込むだけです.
時間の複雑さには大きな違いがあります