ダイナミックプログラミング(DP)

重複演算を減らす

コンピュータの演算速度は限られており、メモリスペースで使用されるデータの数も限られており、多くの制限が発生しています.そのため、演算速度とメモリ空間を最大限に利用する効率的なアルゴリズムを作成する必要があります.
しかし、メモリ容量を増やすことで演算速度を節約できる問題があります.代表的な方法はダイナミックプログラミング技術である.
ダイナミックプログラミングには2つの方法があります(top-downとbottup).
動的プログラミングで解決できる典型的な例は、フィボナッチ数列である.フィボナッチ数列は、前の2つの項の和を現在の項に設定した特徴的な数列である.現在の項目を点火式で以前の項目として表すことができます.例えば、フィボナッチ数列の点火式は、

プログラミングでは、これらの数列を配列またはリストとして表すことができます.数列自体がルールに従って並ぶ数なので.
数学的点火式をプログラミングで表現し,再帰関数を用いるのは簡単である.

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

しかし,このようにフィボナッチ数列を記述するソースコードは深刻な問題を生じる.f(n)関数ではnが大きいほど実行時間が幾何級数で増加するからである.例えば、N=30の場合、約10億の演算が必要となる.再帰関数を用いてフィボナッチ数列の点火式を構築することは可能であるが,単純に毎回計算すると問題を効果的に解決することはできない.動的プログラミングを使用すると、これらの問題を効果的に解決できます.ただし、ダイナミックプログラミングを常に使用することはできません.次の条件を満たす場合に使用できます.

の大きな問題を小さな問題に分けることができます.

小問題から求めた答えは,それを含む大問題においても同様である.

フィボナッチ数列はこれらの条件を満たす代表的な問題である.この問題を解決するには、コメント作成方法を使用します.アノテーションは、一度に得られた結果をメモリ空間に記録し、同じ式を再び呼び出すことで、アノテーションの結果を直接得ることができることを意味する動的プログラミングを実現する方法です.注記は現在、値を格納する方法であるため、キャッシュとも呼ばれます.

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

# 피보나치 함수를 재귀함수로 구현(탑다운 DP)
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]
   
print(pibo(99))

要するに,ダイナミックプログラミングは大きな問題を小さな問題に分け,同じ問題であれば1回の問題を解くだけで効果的に問題を解決できるアルゴリズムである.実際,高速ソートでは大きな問題を小さな問題に分ける方法も紹介されている.クイックソートでは、ソートを実行するときにソートするリストを分割し、全体的なソートにすることができます.これは分割征服アルゴリズムに分類される.動的プログラミングと分割征服の違いは,動的プログラミングが問題が相互に影響することにある.
クイックソートの場合、データム要素が位置を変更して配置されると、そのピボット値を再処理する問題はありません.逆に,動的プログラミングの特徴は,かつて解決した問題を再解決することである.そのため、解決した部分の問題の答えを保存し、この問題が解決したと返し、これ以上解決する必要はありません.たとえば、再帰関数を使用する方法では、一度に解いた問題が結果を保存し、後で同じ問題を解く必要がある場合に保存した値を返します.
再帰関数を使用すると、コンピュータシステムが関数を再呼び出すときにメモリにロードされる一連のプロセスに従う必要があり、オーバーヘッドが発生する可能性があります.したがって、再帰関数ではなく重複文を使用してオーバーヘッドを削減できます.一般的に、重複文を使用するダイナミックプログラミングのパフォーマンスが優れているからです.
動的プログラミングを適用した場合のフィボナッチ数列アルゴリズムの時間的複雑さはO(N)である.

タワー

d = [0] * 100

def fibo(x):
   print('f(' + str(x) + )', end=' ')
   if x == 1 or x == 2:
      return 1
   if d[x] != 0:
      return d[x]
   d[x] = pibo(x-1) + pibo(x-2)
   return d[x]
   
pibo(6)

# 출력 값
f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

このような再帰関数を用いて動的プログラミングソースコードを記述する方法を,小さな問題を呼び出して大きな問題を解決する方法と呼ぶ.逆に,単純に繰り返し文を用いてソースコードを記述すると,小さな問題から逐次漸進的に答えが得られるため,基準上昇方式と呼ぶ.

昇降方式

d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

for i in range(3, n+1):
   d[i] = d[i - 1] + d[i - 2]

print(d[n])

上下(注記)方式を「下入」、下入方式を「上入」と呼びます.ダイナミックプログラミングの典型的な形式はスタンド方式である.「基準上昇」方式で使用した結果格納リストを「DPテーブル」と呼び、注記現在は「下降」方式のみで使用されている表現です.