DAA-動的計画法

動的計画法は、最適化問題でも使用されます。分割統治法と同様に、動的計画法はサブ問題の解を組み合わせることによって問題を解決します。さらに、動的計画法アルゴリズムは、各サブ問題を1回だけ解決してから、その回答をテーブルに保存するため、毎回回答を再計算する作業を回避できます。

問題の2つの主要な特性は、与えられた問題が動的計画法を使用して解決できることを示唆しています。これらのプロパティはoverlapping sub-problems and optimal substructure

重複するサブ問題

分割統治法と同様に、動的計画法もサブ問題の解決策を組み合わせます。これは主に、1つのサブ問題の解決が繰り返し必要な場合に使用されます。計算された解はテーブルに保存されるため、これらを再計算する必要はありません。したがって、この手法は、重複するサブ問題が存在する場合に必要です。

たとえば、二分探索には重複するサブ問題はありません。一方、フィボナッチ数の再帰的プログラムには、多くの重複するサブ問題があります。

最適な部分構造

与えられた問題の最適解がそのサブ問題の最適解を使用して得られる場合、与えられた問題は最適部分構造特性を持っています。

たとえば、最短経路問題には次の最適な部分構造特性があります。

ノードの場合 x ソースノードからの最短パスにあります u 宛先ノードへ v、次にからの最短経路 uv からの最短経路の組み合わせです ux、およびからの最短経路 xv

Floyd-WarshallやBellman-Fordなどの標準のAllPair Shortest Pathアルゴリズムは、動的計画法の典型的な例です。

動的計画法アプローチのステップ

動的計画法アルゴリズムは、次の4つのステップを使用して設計されています-

  • 最適解の構造を特徴付けます。
  • 最適解の値を再帰的に定義します。
  • 通常はボトムアップ方式で、最適解の値を計算します。
  • 計算された情報から最適解を構築します。

動的計画法アプローチの応用

  • 行列の連鎖乗積
  • 最長共通部分列
  • 巡回セールスマン問題