動的プログラミング：特性、例、利点、欠点 - 技術 - 2025

動的プログラミングは、複雑な問題を解決するモデルアルゴリズムであることで割ることを、結果を再計算することを避けるために、その結果を格納する、部分問題に。

このスケジュールは、問題を類似のサブ問題に分割できる場合に使用され、その結果を再利用できます。ほとんどの場合、このスケジュールは最適化に使用されます。

動的プログラミング。フィボナッチ数列に重ね合わされた部分問題。ソース：ウィキメディアコモンズ、en：ユーザー：Dcoatzee、ユーザーがトレース：Stannered / Public domain

利用可能な部分問題を解く前に、動的アルゴリズムは以前に解かれた部分問題の結果を調べようとします。副問題のソリューションが組み合わされて、最適なソリューションが実現されます。

同じ副問題を何度も計算する代わりに、この副問題が最初に発生したときに、ソリューションをメモリに保存できます。別の副問題の解決中に再び現れた場合、すでにメモリに保存されている解決策が採用されます。

これは、メモリ時間を修正するための素晴らしいアイデアです。追加のスペースを使用すると、解決策を見つけるために必要な時間を改善できます。

動的プログラミングの機能

次の基本的な特性は、動的プログラミングを適用する前に問題がなければならないものです。

最適な部分構造

この特性は、最適化問題がそれを構成する二次問題の最適解を組み合わせることによって解決できることを表しています。これらの最適な部分構造は、再帰によって記述されます。

たとえば、グラフでは、頂点sから頂点tに至る最短経路rに最適な部分構造が表示されます。

つまり、この最短経路rでは、任意の中間頂点iをとることができます。rが本当に最短ルートの場合、サブルートr1（sからiへ）とr2（iからtへ）に分割できます。これにより、これらは対応する頂点間の最短ルートになります。

したがって、最短経路を見つけるために、ソリューションを簡単に再帰的に定式化できます。これは、フロイドワーシャルアルゴリズムが行うことです。

重複するサブ問題

副問題空間は小さくなければなりません。つまり、問題を解決する再帰的アルゴリズムは、新しいサブ問題を生成するのではなく、同じサブ問題を何度も解決する必要があります。

たとえば、フィボナッチ数列を生成するには、F1 = F（n – 1）+ F（n – 2）という再帰的な定式化を検討できます。F1= F2 = 1をベースケースとすると、F33 = F32 + F31、およびF32 = F31 + F30。

ご覧のとおり、F31はF33とF32の両方の再帰サブツリーに解決されています。サブ問題の総数は本当に少ないですが、このような再帰的なソリューションを採用すると、同じ問題を何度も何度も解決することになります。

これは動的プログラミングで考慮されるため、各副問題は1回だけ解決されます。これは、次の2つの方法で実現できます。

トップダウンアプローチ

問題の解がその副問題の解を使用して再帰的に定式化でき、これらの副問題が重複している場合、副問題の解を簡単に記憶またはテーブルに格納できます。

新しい副問題の解が検索されるたびに、テーブルは以前に解決されたかどうかを確認するためにチェックされます。ソリューションが保存されている場合は、再度計算する代わりに使用されます。それ以外の場合は、副問題が解決され、ソリューションがテーブルに格納されます。

ボトムアップアプローチ

問題の解がその副問題に関して再帰的に定式化された後、上向きに問題を再定式化しようとすることが可能です。最初に、副問題を解決し、それらの解を使用してより大きな副問題の解に到達することを試みます。

これは通常、表形式でも行われ、小さな副問題の解を使用することにより、より大きな副問題の解を繰り返し生成します。たとえば、F31とF30の値がすでにわかっている場合、F32の値を直接計算できます。

他の手法との比較

動的プログラミングで解決できる問題の重要な特徴の1つは、サブ問題が重複していることです。これが、動的プログラミングと分割統治技術を区別するものであり、最も単純な値を格納する必要はありません。

基本ケースを計算する場合、最終値は帰納的に決定できるため、これは再帰に似ています。このボトムアップアプローチは、新しい値が以前に計算された値のみに依存する場合にうまく機能します。

例

1に到達するための最小ステップ

正の整数「e」の場合、次の3つのステップのいずれかを実行できます。

-数から1を引きます。（e = e-1）。

-2で割り切れる場合、2で割ります（e％2 == 0の場合、e = e / 2）。

-3で割り切れる場合、3で割ります（e％3 == 0の場合、e = e / 3）。

上記の手順に基づいて、eを1にするためにこれらの手順の最小数を見つける必要があります。次に例を示します。

-e = 1の場合、結果：0。

-e = 4の場合、結果：2（4/2 = 2/2 = 1）。

-e = 7の場合、結果：3（7-1 = 6/3 = 2/2 = 1）。

フォーカス

nをできるだけ低くするステップを常に選択し、1に達するまでこのように続けることを考えるかもしれません。しかし、この戦略はここでは機能しないことがわかります。

たとえば、e = 10の場合、ステップは10/2 = 5-1 = 4/2 = 2/2 = 1（4ステップ）になります。ただし、最適な形式は10-1 = 9/3 = 3/3 = 1（3ステップ）です。したがって、見つかったnの値ごとに実行できるすべてのステップを試して、これらの可能性の最小数を選択する必要があります。

すべては再帰から始まります：F（e）= 1 + min {F（e-1）、F（e / 2）、F（e / 3）} e> 1の場合、基本ケースとして：F（1） =0。再帰方程式があるので、再帰のコーディングを開始できます。

ただし、サブ問題が重複していることがわかります。さらに、特定の入力の最適解は、その副問題の最適解によって異なります。

記憶のように、解決された副問題の解は後で使用するために保存されます。または、動的プログラミングの場合と同様に、一番下から始めて、与えられたeまで進みます。次に両方のコード：

暗記

ダイナミックボトムアッププログラミング

利点

動的プログラミングを使用する主な利点の1つは、以前に計算された参照が使用されるため、処理が高速化されることです。これは再帰的なプログラミング手法であるため、プログラム内のコード行を減らします。

貪欲なアルゴリズムと動的プログラミング

貪欲なアルゴリズムは、どちらも最適化のためのツールであるという点で動的プログラミングに似ています。ただし、貪欲なアルゴリズムは、各ローカルステップで最適なソリューションを探します。つまり、グローバルな最適を見つけることを期待して、貪欲な選択を求めます。

したがって、貪欲なアルゴリズムは、その時点では最適に見えるが、将来は高価になり、全体的な最適を保証しないという仮定を立てることができます。

一方、動的計画法は、副問題の最適な解を見つけ、それらの副問題の結果を組み合わせて、情報に基づいた選択を行い、実際に最も最適な解を見つけます。

短所

-各サブ問題の計算結果を保存するには、保存された値が使用されるかどうかを保証できないため、大量のメモリが必要です。

-多くの場合、出力値は実行中に次のサブ問題で使用されることなく保存されます。これは、不必要なメモリ使用につながります。

-動的プログラミングでは、関数は再帰的に呼び出されます。これにより、スタックメモリが常に増加し続けます。

再帰vs動的プログラミング

コードを実行するためのメモリが限られていて、処理速度が問題にならない場合は、再帰を使用できます。たとえば、モバイルアプリケーションを開発している場合、メモリはアプリケーションを実行するために非常に制限されます。

プログラムをより高速に実行し、メモリ制限がない場合は、動的プログラミングを使用することをお勧めします。

用途

動的計画法は、妥当な時間内に解決するのが非常に難しいと思われる問題を効果的に解決する方法です。

動的プログラミングパラダイムに基づくアルゴリズムは、問題解決の計画から音声認識まで、人工知能の多くの例を含む科学の多くの領域で使用されています。

動的計画法に基づくアルゴリズム

動的プログラミングは非常に効果的で、さまざまな問題に対して非常に効果的です。多くのアルゴリズムは、次のような貪欲なアルゴリズムアプリケーションと見なすことができます。

-フィボナッチ数シリーズ。

-ハノイの塔。

-フロイドワーシャルを通る短いルートのすべてのペア。

-バックパックの問題。

-プロジェクトのスケジュール。

-ダイクストラを通る最短の方法。

-飛行制御とロボット制御。

-数学的最適化問題。

-タイムシェア：ジョブをスケジュールして、CPU使用率を最大化します。

フィボナッチ数列

フィボナッチ数列は、0、1、1、2、3、5、8、13、21、34、55、89、144などのシーケンスで見つかった数です。

数学用語では、フィボナッチ数列のシーケンスFnは、次の漸化式で定義されます：F（n）= F（n -1）+ F（n -2）、ここでF（0）= 0およびF（ 1）= 1。

トップダウンアプローチ

この例では、すべての初期値を持つ検索配列は-1で初期化されます。副問題の解が必要なときはいつでも、この探索行列が最初に探索されます。

計算された値がある場合は、その値が返されます。それ以外の場合は、結果を計算して検索マトリックスに格納し、後で再利用できるようにします。

ボトムアップアプローチ

この場合、同じフィボナッチシリーズの場合、f（0）が最初に計算され、次にf（1）、f（2）、f（3）などが計算されます。したがって、副問題の解決策はボトムアップで構築されています。

参考文献

1. Vineet Choudhary（2020）。動的プログラミング入門。Developer Insider。次から取得：developerinsider.co。
2. アレックスアレイン（2020）。C ++での動的プログラミング。Cプログラミング。取得元：cprogramming.com。
3. アカデミーの後（2020）。動的プログラミングのアイデア。取得元：afteracademy.com。
4. Aniruddha Chaudhari（2019）。動的プログラミングと再帰-違い、例による利点。CSEスタック。取得元：csestack.org。
5. コードシェフ（2020）。動的プログラミングのチュートリアル。取得元：codechef.com。
6. Programiz（2020）。動的プログラミング。取得元：programiz.com。