動的プログラミングアルゴリズムのルーチンをマスターするにはどうすればいいですか?

[[358211]]

DP と呼ばれる動的プログラミングは、非常に洗練された複雑なアルゴリズムという印象を与えます。多くの学生はこの名前を見ると落胆し、面接で動的プログラミングについて質問されることを非常に恐れます。実際、それは明確なアルゴリズムではなく、問題を最適な方法で解決するためのアイデアまたは方法です。これは、アメリカの数学者ベルマンが多段階の意思決定プロセスの最適化問題を研究していたときに提案されました。ただし、線形計画法、非線形計画法など、時間に依存しない静的な計画法もいくつかあります。オペレーションズリサーチにおいて、動的計画法は非常に重要な内容であり、さまざまな業界で広く使用されています。動的プログラミングをどのように理解すればよいでしょうか?

問題の最適解がそのサブ問題の最適解から導き出せる場合、まずそのサブ問題の最適解を見つけ、次にサブ問題の解に基づいて元の問題の最適解を得ることができます。サブ問題が繰り返し出現する場合、繰り返し計算を減らして時間計算量を減らすために、最終的なサブ問題から元の問題まで下から上に向かって段階的に解決し、サブ問題を先に保管することができます。大きなサブ問題を解決するときは、テーブルからサブ問題の解を直接照会することができます。これが動的プログラミングの基本的な考え方です。

簡単に言えば、大きな問題がいくつかのサブ問題に簡略化されてテーブルに保存され、データ テーブル内のサブ問題の解決策に基づいて大きな問題の解決策が見つかります。このアルゴリズムは見覚えがありますか? 実際、動的プログラミングは分割統治アルゴリズムに似ており、分割統治アルゴリズムと比較されることがよくあります。これらすべてをいくつかのサブ問題に分解し、サブ問題を解決する必要があります。違いは、分割統治アルゴリズムが各サブ問題を上から下へ解決し、サブ問題の解決策をマージして元の問題の解決策を取得するのに対し、動的プログラミングはサブ問題を分解し、サブ問題の解決策を下から上へ解決し、結果を保存することです。大きなサブ問題を解決するときは、サブ問題の解決策を直接照会できるため、アルゴリズムの効率が大幅に向上します。

理論的な説明は堅苦しくてつまらないので、例を見てみましょう。

フィボナッチ数列

フィボナッチ数列

フィボナッチ数列は非常に不思議な数列です。イタリアの数学者レオナルド・フィボナッチによって提唱されました。その特徴は、数列内の特定の項目の値が、前の 2 つの項目の合計であることです。黄金比数列とも呼ばれます。

[[358213]]

レオナルド・フィボナッチ

フィボナッチ数列は次の一般式で表すことができます。

フィボナッチ数列の式から、数列のn番目（n>2）の項の値f(n)はf(n)+f(n-1)に等しいことがわかります。f(n)の値を取得するには、まずf(n-1)とf(n-2)の値を見つける必要があります。分析のため、n=6と仮定します。下の図に従って、段階的に小さな値に分解できます。

フィボナッチ

上の図を見た後、誰もがプログラムの実装のアイデアを頭の中に持っていると思います。再帰メソッドを直接使用して、n 個のアイテムの値を検索できます。以下に示すように、プログラムは非常に簡単です。

 int fib( int n)
 {
    n==1 || n==2の場合、 1を返します。
 fib(n-1) + fib(n-2) を返します。
 }

しかし、このアルゴリズムは O(2^n) という指数関数的な時間計算量を持ち、n が増加すると計算量も指数関数的に増加します。n が一定のサイズに達すると、非常に長い時間がかかります。明らかに、これは最適なアルゴリズムではありません。しかし、上図の分解項目をよく見ると、図には繰り返されるサブ項目が多数あることがわかります。これが、上記の再帰アルゴリズムの複雑性が比較的高い理由です。では、最適化はまだ可能でしょうか? 答えは「はい」です。

上記のアルゴリズムは、動的プログラミングの考え方によって最適化できます。 多数の繰り返し計算を回避するために、最下位レベルのサブ問題から始めて、これらのサブ問題の値をテーブルに保存することができます。 この値に再び遭遇したときに、再計算する必要はありません。

次のプログラムに示すように、最小のサブ問題 n=1,2 から計算を開始し、計算されたサブ問題の値を格納するベクトル コンテナーを定義します。次に大きな問題を計算するときに、コンテナー内の値を直接呼び出すことができます。

 int fib( int n)
 {
    ベクトル< int > dp(n, 0); 
 
    dp[0] = dp[1] = 1;
 ( int i = 2; i < n; i++)の場合
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    } 
 
 dp[n-1]を返します。
 }

明らかに、上記のアルゴリズムはアルゴリズムの時間計算量を大幅に削減し、時間計算量は O(n) になりました。ただし、時間の複雑さは軽減されますが、スペースを犠牲にして実現されます。実は、さらに最適化することができます。式から、特定の項目の値を見つけるには、まず最初の 2 つのサブ問題の値を見つける必要があることがわかります。サブ問題を下から上に解くと、連続する 2 つのサブ問題の値を直接保存できます。

 int fib( int n)
 {
整数dp[2]={1,1}; 
 
 ( int i = 2; i < n; i++)の場合
    {
 tmp = dp[0];
        dp[0] = dp[1];
        dp[1] = dp[1] + tmp;
    } 
 
 dp[1]を返す。
 }

最長増加部分列

厳密に言えば、上記のフィボナッチ数列は完全に動的計画法の問題ではありません。動的計画法の定義によれば、動的計画法の問題は一般に次の 3 つの特性を満たします。

• 最適化の原理: 元の問題の最適解によって分解されたサブ問題の解も最適である場合、その問題は最適なサブ構造を持ち、サブ問題の最適解から元の問題の最適解を導き出すことができるといえます。
• 後遺症なし: ある段階の状態が決定されると、その状態が将来の決定に与える影響は現在の状態のみに関連します。
• 重複するサブ問題があります: サブ問題は、意思決定の次の段階で繰り返し使用される可能性があります。

動的計画法の問題のこれら 3 つの特性に基づいて、別の例である、非常に古典的な動的計画法の問題である最長増加部分列問題 (LIS と略記) を見てみましょう。

長さ n のシーケンス a0、a1、...、a(n-1) があります。このシーケンス内の最長の増加部分シーケンスの長さを求めます。いわゆる昇順部分列とは、任意のi

まず、次の表に示すように、元の問題を順にサブ問題に分解します。

後続

コードは次のように実装できます。dp配列を使用して、nums[i]で終わる最長サブシーケンスの長さを保存し、maxに最長サブシーケンスの長さを格納します。

 int maxLIS(std::vector< int >& 数値)
 {
整数 最大値= 1;
    std::vector< int > dp(nums.size ( ), 1); 
 
 ( int i = 1; i< nums.size ( ) ); i++)の場合
    {
 ( int j=0; j<i; j++)の場合
        {
            数値[i]>数値[j]の場合
            {
                dp[i] = dp[j] + 1;
            }
 std:: maxは、 dp[i] とstd ::max の積です。
        }
    } 
 
戻る 最大;
 }

上記の 2 つの例から十分に理解できましたか? ナップサック問題、コインの両替、最短経路など、動的プログラミングを使用して解決できる一般的な問題はたくさんあります。動的プログラミングは固定されたアルゴリズムではなく、対応する問題も多様ですが、基本的な考え方を習得すれば、対応する問題を簡単に解決できます。今すぐ試してみましょう。

この記事はWeChat公式アカウント「Will's Canteen」から転載したものです。下のQRコードからフォローできます。この記事を転載する場合は、Will’s Dashitang パブリックアカウントにご連絡ください。