Data-structures-algorithms-dynamic-programming

データ構造-動的プログラミング

動的プログラミングのアプローチは、問題をより小さな、さらに小さな可能なサブ問題に分解する点で、分割して征服することに似ています。 しかし、分割して征服するのとは異なり、これらの副問題は独立して解決されません。 むしろ、これらの小さな副問題の結果は記憶され、類似または重複する副問題に使用されます。

動的プログラミングは、問題がある場合に使用されます。問題は同様のサブ問題に分けられ、その結果を再利用できます。 ほとんどの場合、これらのアルゴリズムは最適化に使用されます。 手持ちの副問題を解決する前に、動的アルゴリズムは以前に解決された副問題の結果を調べようとします。 最適なソリューションを実現するために、サブ問題のソリューションが組み合わされます。

だから我々はそれを言うことができます-

• 問題は、より小さな重複する副問題に分割できる必要があります。
• より小さいサブ問題の最適なソリューションを使用することにより、最適なソリューションを実現できます。
• 動的アルゴリズムはメモ化を使用します。

比較

局所的な最適化に対処する貪欲なアルゴリズムとは対照的に、動的アルゴリズムは問題の全体的な最適化に動機付けられます。

ソリューションを組み合わせて全体的なソリューションを実現する分割統治アルゴリズムとは対照的に、動的アルゴリズムは小さなサブ問題の出力を使用してから、大きなサブ問題の最適化を試みます。 動的アルゴリズムは、メモ化を使用して、すでに解決された副問題の出力を記憶します。

例

次のコンピュータの問題は、動的プログラミングのアプローチを使用して解決することができます-

• フィボナッチ数列
• ナップザック問題
• ハノイの塔
• フロイド・ワーシャルによる全ペア最短経路
• ダイクストラによる最短経路
• プロジェクトのスケジューリング

動的プログラミングは、トップダウン方式とボトムアップ方式の両方で使用できます。 もちろん、ほとんどの場合、以前のソリューションの出力を参照する方が、CPUサイクルの観点から再計算するよりも安価です。