データ構造-動的計画法

動的計画法のアプローチは、分割統治法に似ており、問題をより小さな、さらにはより小さな可能なサブ問題に分解します。しかし、分割統治法とは異なり、これらのサブ問題は独立して解決されません。むしろ、これらの小さなサブ問題の結果が記憶され、類似または重複するサブ問題に使用されます。

動的計画法は、問題が発生した場合に使用されます。問題は、同様のサブ問題に分割できるため、結果を再利用できます。ほとんどの場合、これらのアルゴリズムは最適化に使用されます。手元のサブ問題を解決する前に、動的アルゴリズムは以前に解決されたサブ問題の結果を調べようとします。最良の解決策を達成するために、サブ問題の解決策が組み合わされます。

だから私たちはそれを言うことができます-

• 問題は、より小さな重複するサブ問題に分割できるはずです。

• 最適なソリューションは、より小さなサブ問題の最適なソリューションを使用することで実現できます。

• 動的アルゴリズムはメモ化を使用します。

比較

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

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

例

以下のコンピューターの問題は、動的計画法を使用して解決できます。

• フィボナッチ数列
• ナップサック問題
• ハノイの塔
• Floyd-Warshallによるすべてのペアの最短経路
• ダイクストラによる最短経路
• プロジェクトのスケジューリング

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