Design-and-analysis-of-algorithms-dynamic-programming

DAA-動的プログラミング

動的プログラミングは、最適化問題でも使用されます。 分割統治法と同様に、動的計画法は、部分問題の解決策を組み合わせることで問題を解決します。 さらに、ダイナミックプログラミングアルゴリズムは各副問題を一度だけ解決し、その回答をテーブルに保存するため、毎回回答を再計算する作業を回避できます。

問題の2つの主な特性は、与えられた問題が動的計画法を使用して解決できることを示唆しています。 これらのプロパティは、*重複するサブ問題と最適なサブ構造*です。

重複するサブ問題

分割統治アプローチと同様に、ダイナミックプログラミングもサブ問題のソリューションを組み合わせます。 主に、1つの副問題の解決が繰り返し必要な場合に使用されます。 計算されたソリューションはテーブルに保存されるため、これらを再計算する必要はありません。 したがって、重複する副問題が存在する場合、この手法が必要です。

たとえば、バイナリ検索には重複する副問題はありません。 一方、フィボナッチ数の再帰プログラムには、多くの重複する副問題があります。

最適なサブ構造

与えられた問題の最適解がその副問題の最適解を使用して得られる場合、与えられた問題には最適な部分構造プロパティがあります。

たとえば、最短経路問題には、次の最適な部分構造プロパティがあります-

ノード x がソースノード u から宛先ノード v への最短パスにある場合、 u から v への最短パスは u から*への最短パスの組み合わせです。 x 、および *x から v への最短パス。

Floyd-WarshallやBellman-Fordなどの標準的な全ペア最短パスアルゴリズムは、動的プログラミングの典型的な例です。

動的プログラミングアプローチの手順

ダイナミックプログラミングアルゴリズムは、次の4つのステップを使用して設計されています-

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

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

• 行列チェーンの乗算
• 最長共通部分列
• 巡回セールスマン問題