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

ダイナミックプランニングアルゴリズムは、問題をいくつかの小さな問題に分け、同じ問題であれば一度だけ解いてから、解の結果を格納し、大きな問題の結果と統合して、効果的に問題を解決するアルゴリズムです.
コンピュータの演算速度は限られており、メモリ空間で使用されるデータの数も限られているため、演算速度とメモリ空間を最大限に利用するための効率的なアルゴリズムを作成する必要があります.
しかし、メモリ容量を増やすことで演算速度を節約できる問題があります.最も代表的な方法はダイナミックプログラミング(Dynamic Programming)技術であり、ダイナミックプランニング法とも呼ばれている.
動的プログラミングで解決できる典型的な例は、フィボナッチ数列である.フィボナッチ数列は、前の2つの項の和を現在の項に設定した特徴的な数列である.点火式は隣接項間の関係式であり,点火式を用いて数列項の継続形式を表すことができる.
フィボナッチ数列の点火式は、

n次フィボナッチ数=(n-1)次フィボナッチ数+(n-2)次フィボナッチ数
ただし、1番目のフィボナッチ数=1、2番目のフィボナッチ数=1
数学的点火式をプログラミングで表現し,再帰関数を用いるのは簡単である.

# 피보나치 함수를 재귀 함수로 구현
def fibo(x):
	if x == 1 or x == 2:
    	return 1
    return fibo(x-1) + fibo(x-2)

しかし,このようにフィボナッチ数列のソースコードを記述すると,nが大きくなるにつれて実行時間は幾何級数的に増加し,一般にO(2^n)の指数時間として表される.この場合,同じn個のfibo(n)関数を内部で繰り返し呼び出すことが分かる.
再帰関数を使用してFie波奇数列の点火式を作成することはできるが,単純な計算のたびに問題を効果的に解決することはできない.動的プログラミングを使用すると、これらの問題を効果的に解決できます.
動的プログラミングは、次の条件を満たすために使用できます.
1.大きな問題を小さな問題に分けることができます.
2.小さな質問で求めた答えは、それを含む大きな質問でも同じです.
大きな問題を小さな問題に分割する方法は,高速ソートを実行する際にソートリストを分割して全体的にソートできるようにする方法であり,この方法は分割征服(Divide and Conquer)アルゴリズムに分けられる.動的プログラミングと分割征服の違いは,動的プログラミングが問題が相互に影響することにある.
フィボナッチ数列はこれらの条件を満たす代表的な問題であり,Memoization技術を用いて解決できる.アノテーションは、一度に得られた結果をメモリ空間に記録し、同じ式を再び呼び出すことで、アノテーションの結果を直接得ることができることを意味する動的プログラミングを実現する方法です.注記は値を格納する方法であるため、キャッシュとも呼ばれます.
得られた情報をリストに保存し,動的プログラミングを行い,同じ情報が必要であれば,リストから得られた答えを直接取得することができる.

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
	# 종료 조건(1 혹은 2일 때 1을 반환)
	if x == 1 or x == 2:
    	return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
    	return d[x]
    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]
    

再帰関数を使用すると、コンピュータシステムが関数を再呼び出すときにメモリにロードされる一連のプロセスに従う必要があり、オーバーヘッドが発生する可能性があります.したがって、再帰関数ではなく重複文を使用してオーバーヘッドを削減できます.一般的に、重複文を使用するダイナミックプログラミングのパフォーマンスが優れているからです.では,動的プログラミングを適用する際のフィボナッチ数列アルゴリズムの時間的複雑度はO(N)である.一度に求めた結果は再び求められないので、まずf(1)を求め、その後、その値をf(2)を解くために用い、f(2)の値をf(3)を解くために接続する.
このように再帰関数を用いて動的プログラミングソースコードを記述する方法は,大きな問題を解決するために小さな問題を呼び出しtop−down方式と呼ぶ.逆に,単純に重複文を用いてソースコードを記述すると,小さな問題から答えが出てくるため,「Bottom-Up」方式と呼ぶ.フィボナッチ数列問題を下から上へbottumup方式で解き,以下に示す.

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

 # 피보나치 함수 반복문으로 구현(보텀업 다이나믹 프로그래밍)
 for i in range(3, n+1):
 	d[i] = d[i-1] + d[i-2]

上下(注記)方式を「下入」、下入方式を「上入」と呼びます.ダイナミックプログラミングの典型的な形式はスタンド方式である.「基準上昇」方式で使用した結果格納リストを「DPテーブル」と呼び、注記現在は「下降」方式のみで使用されている表現です.厳密には,注釈化は動的プログラミングとは異なり,以前計算した結果を一時的に記録できる広い概念である.
辞書(dict)資料型など、手帳には他の資料型が使用される場合があります.辞書型は数列ほど連続していない場合に役立ちます.
フルナビゲーションアルゴリズムを使用して問題にアクセスする場合、時間がかかる場合は、動的プログラミングを適用できるかどうかを判断するために、重複する問題の一部があるかどうかを確認します.
再帰関数を用いて効率の低いプログラムを記述すると,小さな問題の答えは大きな問題で依然として利用可能であり,すなわち注釈転送を適用できればコードを改善することができる.可能であれば,再帰関数を用いたタワー法ではなく,基準を上にして実施することを提案する.システム上の再帰関数のスタックサイズは限られている可能性があるからです.この場合、sysライブラリに含まれるsetrecursionlimit()関数を呼び出すことで、再帰的な制限を緩和できます.
動的プログラミングアルゴリズムは,問題を解決する最適な解決法が局所問題の最適な解決法からなる場合の問題,すなわち最適な局所構造を有する問題を解決することができる.最適部分構造を解く別のアルゴリズムはGRADYアルゴリズムである.グリッディアルゴリズムは常にその瞬間に自分が最適だと思っているものを選んで解くが,動的プログラム設計の違いは,重複するサブ問題(Overlapping Subproblem)の結果を保存してから解くことである.ここでのポイントは「重複する」問題であり,重複しない問題は動的プログラミングによって解決されない.代表的なのは,マージソートや高速ソートなどであり,それらは分割征服アルゴリズムに分類される.