動的プログラミングとは

動的プログラミングは、コンピューターサイエンスの分野を指す場合、問題をより小さな問題のセットに分解することによって複雑な問題を解決することを目的とした類似のコンピューターアルゴリズムのグループを表します。 1950年代に最初にリチャードベルマンによって作成されたダイナミックプログラミングは、重複する部分問題または最適な部分構造のいずれかの問題を処理します。 動的プログラミングがどのように機能するかを理解するには、これら2つの用語の背景にある概念を理解することが最善です。

重複するサブ問題は、複雑な方程式を記述します。複雑な方程式は、小さな方程式のセットに分解されると、小さな方程式の一部を複数回再利用して答えを出します。 たとえば、一連の数値を使用してすべての可能な結果を​​計算するように指示された数式は、同じ結果を何度も計算し、他の結果を1回だけ計算する場合があります。 ダイナミックプログラミングでは、最初に結果を計算した後、その結果を保存し、後で計算するのではなく、後で方程式に答えを挿入する必要があるという問題を伝えます。 長く複雑なプロセスと方程式を扱う場合、これは時間を節約し、はるかに少ないステップでより高速なソリューションを作成します。

最適な下位構造は、すべての下位問題に対するベストアンサーを見つけて、全体的なベストアンサーを作成することにより、ソリューションを作成します。 複雑な問題を小さな問題に分解した後、コンピューターは数学システムを使用して、各問題の最良の答えを決定します。 より小さい回答から元の問題に対する回答を計算します。 このプロセスには欠陥が存在します。 数学的に最適に機能するソリューションを提供しますが、問題の種類とそれが実際の世界とどのように関係するかに応じて、実際の生活で最良のソリューションである場合とそうでない場合があります。

これらの操作のいずれかで、動的プログラミングアルゴリズムはソリューションへの最短パスを見つけようとします。 これを行うには、2つのアプローチのいずれかを使用できます。 トップダウンアプローチは、方程式をより小さな方程式に分解し、必要に応じてこれらの方程式の答えを再利用します。 ボトムアップアプローチは、方程式を分割した後、最小の数学値を解こうとし、そこから最大に向かって上昇します。 どちらのアプローチも時間を節約しますが、動的プログラミングは、元の問題が方程式を解くためにある時点で再利用される小さな方程式に分解できる場合にのみ機能します。