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

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

• 
  

  メモリ容量を増やすことで演算速度を向上させる問題があります.

  
  
  • の代表的な手法がダイナミックプログラミングの手法でダイナミックプランニング法として表現されることもある.
  
  
• 
  

  の代表的な例はフィボナッチ数列である.

  
  
  • 
    

    フィボナッチ数列は、前の2つの項目の和を現在の項目に設定した数列です.

    
    
  • 
    

    数学者たちは、数列項の継続形式を点火式で簡潔に表現している.

    
    
    • 点火式とは、隣接する項間の関係式を指す.
    
    
  • 
    

    フィボナッチ数列の点火式は以下の通りである:
    
    

    
    

    

    
    
  
  

• 
  

  プログラミングは、これらの数列を配列またはリストとして表すことができる.

  
  
  • の数列自体がルールに従って並んでいるからです.
  
  
• 
  

  数学的点火式をプログラミングで表現するには,再帰関数を用いるのが簡単である.p>
  

def fibo(x):
    if x == 1 or x == 2:
    	return 1
    return fibo(x - 1) + fibo(x - 2)
    
print(fibo(4))

• 
  

  しかし、このようにフィボナッチ数列を記述するソースコードは深刻な問題を生じる可能性がある.

  
  
  • 
    

    f(n)関数では、nが大きくなるにつれて実行時間が指数関数的に増加するからである.

    
    
  • 
    

    動的プログラミングを用いることで、これらの問題を効果的に解決することができる.

    
    
  
  

• 
  

  使用条件

  
  

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

  
  

  2. 小さな質問で求めた答えは、それを含む大きな質問でも同じです.

  
  

上下にひっくり返す

• 
  

  再帰関数を用いて動的プログラミングソースコードを記述する方法で、大きな問題を解決するためにtop-down方式と呼ばれる小さな問題を呼び出す.

  
  
• 
  

  単純に繰り返し文を用いてソースコードを記述すると,Boottom−Up方式と呼ばれる小さな問題から逐次漸進的に答えが得られる.p>
  

  • は同様の原理を適用するが,重複文のみを用いて問題を解決すると理解できる.
  
  

注記リビルド(キャッシュ)-タワー(上から下へ)

• のダイナミックプログラミングを実現する方法の1つは、求めた結果をメモリ空間に記録し、再び同じ式を呼び出して、得られた結果をそのままにする方法である.

• 
  

  どのように実施するか

  
  
  • 
    

    取得した情報をリストに保存する

    
    
  • 
    

    動的プログラミングを再帰的に実行する場合、同じ情報が必要な場合は、リストから得られた正解を直接取得できます.

    
    
  
  

d = [0] * 100

def fibo(x):
    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(fibo(99))

• 
  <>まとめると,動的プログラミングは大きな問題を小さな問題に分け,同じ問題であれば1回の問題を解くだけで効果的に問題を解決できるアルゴリズムテクニックである.p>
  
• 
  

  注釈は現在、上から下への表現に限られている.

  
  
  • 
    

    厳密には、注釈は現在、動的プログラミングとは別に、以前の計算結果を一時的に記録することができる広い概念である.

    
    
    • は、動的プログラミングではなく、計算結果をどこかに置くだけです.
    
    
  
  
• 
  

  コメントは、dictデータ型などの他のデータ型を必要に応じて使用できるようになりました.

  
  
  • は、数列ほど連続していない場合に役立ちます.
  
  

星雲-基準上昇(上向き)

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テーブル」と呼ぶ.

  
  

🟡🟢🟡

• 
  

  フルナビゲーションアルゴリズムを使用して特定の問題にアクセスする場合は、時間が長すぎる場合にダイナミックプログラミングを適用できるかどうかの問題を解決するために、重複する問題があるかどうかを確認します.

  
  
• 
  

  低効率なプログラムを再帰関数で簡単に記述し、(topdown)小さな問題の答えを大きな問題で直接使用することができ、すなわち注釈変換を適用できればコードを修正する方法も良いアイデアである.p>
  

• 
  

  可能であれば、インフラストラクチャの採用を推奨します.

  
  
  • 
    

    システムは再帰関数のスタックサイズを制限する可能性があるため.

    
    
  • 
    

    sysライブラリsetrecursionlimit()関数を呼び出すことで、再帰的な制限を緩和できます.