動的プログラミングを理解して効果的に使用できるようにする

この記事は製品開発とは関係ありませんが、プログラミングに関するものです。動的プログラミング (DP) と、これまでの計算経験を効果的に活用する方法について説明します。面白いと思っていただけると幸いです。

動的プログラミングの概要

動的プログラミングという用語は、1950 年代にコンピューター技術の主要な専門家の 1 人である有名なアメリカの数学者、リチャード ベルマンによって初めて使用されました。動的プログラミング (DP) は、複雑なタスクをより小さなサブ問題に分割することで解決する方法です。

DP が解決できる問題の種類は、次の 2 つの基準を満たす必要があります。

1. 最適な下部構造。動的プログラミングとは、より小さな部分問題の解決策を使用して最初の問題を解決できることを意味します。最適な下部構造は、「分割統治」パラダイムの主な特徴です。

典型的な実装例はマージ ソート アルゴリズムです。このアルゴリズムでは、問題を最も単純なサブ問題 (サイズ 1 の配列) に再帰的に分割し、その後、それぞれに基づいて計算を行います。結果は、最初の層が達成されるまで、次の層 (より大きなサブ問題) を解決するために使用されます。

2. 重複するサブ問題。コンピューター サイエンスでは、問題を複数回再利用できるサブ問題に分割できる場合、その問題には重複するサブ問題があると言われます。言い換えれば、同じ入力データと同じ結果を使用して同じコードを実行します。この問題の典型的な例は、以下で説明するフィボナッチ数列の N 番目の要素の計算です。

DP は、分割統治パラダイムの使用の特殊なケース、またはそのより複雑なバージョンであると言うことができます。このパターンは、多数の異なる組み合わせが計算されるものの、N 個の要素が単調で同一であることが多い、組み合わせ論を含むタスクを解決するのに適しています。

最適な部分構造と重複する部分問題の問題では、総当たりアプローチを適用すると、多数の計算と演算が繰り返されます。 DP は、メモ化と表作成という 2 つの主なアプローチを使用して、ソリューションを最適化し、計算量の 2 倍化を回避するのに役立ちます。

1. メモ化 (トップダウン アプローチ)は再帰によって実装されます。タスクは小さなサブ問題に分割され、その結果がメモリに取り込まれ、繰り返し使用することで元の問題を解決するために結合されます。

• 短所:このアプローチでは、再帰的なメソッド呼び出しを通じてスタック メモリが使用されます。
• 長所: DP タスクに対する柔軟性。

2. 集計 (ボトムアップ アプローチ) は反復手法を使用して実装されます。最小の問題から初期の問題まで、連続して反復的に計算されます。

• 短所:適用範囲が限られている。このアプローチでは、一連の部分問題全体を最初に理解する必要があります。しかし、問題によっては、これが不可能な場合もあります。
• 長所:すべてが 1 つの関数内で実行されるため、メモリが効率的に使用されます。

この理論は退屈で理解できないように聞こえるかもしれません。いくつかの例を見てみましょう。

問題: フィボナッチ数列

DP の古典的な例は、フィボナッチ数列の N 番目の要素を計算することです。ここで、各要素は前の 2 つの要素の合計であり、最初と 2 番目の要素は 0 と 1 に等しくなります。

仮説により、1 つの値を計算するには、その前の値を見つける必要があるため、最初は最適な部分構造の性質に焦点を当てます。前の値を計算するには、その前の値を見つける必要があります。以下同様です。重複するサブタスクの性質を以下の図に示します。

このタスクでは、次の 3 つのケースを検討します。

1. 率直なアプローチ: マイナス点は何ですか?
2. メモ化を使用した最適化されたソリューション
3. 集計を使用した最適化されたソリューション

単純明快/強引なアプローチ

最初に思いつくのは、再帰を入力し、先行する 2 つの要素を合計し、その結果を与えることです。

 /** * Straightforward(Brute force) approach */ fun fibBruteForce(n: Int): Int { return when (n) { 1 -> 0 2 -> 1 else -> fibBruteForce(n - 1) + fibBruteForce(n - 2) } }

以下の画面では、シーケンスの 5 番目の要素を計算するための関数呼び出しのスタックが表示されます。

関数fib(1) 5 回呼び出され、 fib(2) 3 回呼び出されることに注意してください。 1 つのシグネチャと同じパラメータを持つ関数は繰り返し起動され、同じことを実行します。 N の数が増加すると、ツリーは線形ではなく指数関数的に増加し、計算が膨大に重複することになります。

数学的分析:

時間計算量: O(2n)、

空間複雑度: O(n) -> 暗黙的な関数呼び出しのスタックに存在できる要素の最大数であるため、再帰ツリーの最大深さに比例します。

結果:このアプローチは非常に非効率的です。たとえば、30 番目の要素を計算するには 1,073,741,824 回の演算が必要です。

メモ化 (トップダウンアプローチ)

このアプローチでは、メモリの割り当てを除いて、実装は前述の「総当たり」ソリューションとそれほど変わりません。これを変数メモとし、スタック内の完了した fib() 関数の計算結果を収集します。

整数の配列を用意し、それをインデックスで参照できれば十分ですが、概念を明確にするためにハッシュ マップが作成されていることに注意してください。

 /** * Memoization(Top-down) approach */ val memo = HashMap<Int, Int>().apply { this[1] = 0 this[2] = 1 } fun fibMemo(n: Int): Int { if (!memo.containsKey(n)) { val result = fibMemo(n - 1) + fibMemo(n - 2) memo[n] = result } return memo[n]!! }

関数呼び出しスタックにもう一度注目してみましょう。

• 結果をメモに書き込む最初に完成した関数は、強調表示されているfib(2)です。強調表示されたfib(3)に制御が戻ります。
• 強調表示されたfib(3) 、 fib(2)とfib(1)の呼び出しの結果を合計した後にその値を見つけ、その解をメモに入力し、制御をfib(4)に返します。
• 以前のエクスペリエンスを再利用する段階に達しました。制御がfib(4)に戻されると、 fib(2)呼び出しはその中での順番を待ちます。 fib(2)は、( fib(1) + fib(0) ) を呼び出す代わりに、メモからの完成したソリューション全体を使用し、それをすぐに返します。
• fib(4)が計算され、 fib(5)に制御が返されます。fib(5) はfib(3)を起動するだけで済みます。最後の例えでは、 fib(3)計算せずにメモからの値を即座に返します。

関数呼び出しと計算の数が減少していることがわかります。また、N が増加すると、減少は指数関数的に少なくなります。

数学的分析:

時間計算量: O(n)

空間の複雑さ: O(n)

結果:漸近的な複雑さには明らかな違いがあります。このアプローチでは、原始的なソリューションと比較して、時間が線形になるまで短縮され、メモリ内での増加はありません。

集計（ボトムアップアプローチ）

上で述べたように、このアプローチには、より小さなサブ問題からより大きなサブ問題への反復計算が含まれます。フィボナッチの場合、最小の「部分問題」はシーケンスの最初と 2 番目の要素、それぞれ 0 と 1 です。

私たちは、要素が互いにどのように関係しているかをよく知っています。これは、式fib(n) = fib(n-1) + fib(n-2)で表されます。前の要素がわかっているので、次の要素、その後の要素などを簡単に計算できます。

私たちが認識している値を合計することで、次の要素を見つけることができます。目的の値が見つかるまで、この操作を周期的に実行します。

 /** * Tabulation(Bottom-up) approach fun fibTab(n: Int): Int { var element = 0 var nextElement = 1 for (i in 2 until n) { val newNext = element + nextElement element = nextElement nextElement = newNext } return nextElement }

数学的分析:

時間計算量: O(n)

空間の複雑さ: O(1)

結果:このアプローチは、速度の点ではメモ化と同じくらい効果的ですが、一定量のメモリを消費します。

問題: 固有のバイナリ ツリー

より複雑な問題を見てみましょう。N 個のノードから作成できる構造的に一意なバイナリ ツリーの数をすべて見つける必要があります。

バイナリ ツリーは階層データ構造であり、各ノードには 2 つ以下の子孫が含まれます。一般に、最初のノードは親ノードと呼ばれ、2 つの子 (左の子と右の子) を持ちます。

N = 3 の解を見つける必要があると仮定します。3 つのノードには、構造的に一意な 5 つのツリーがあります。頭の中で数えることはできますが、Nが増えるとそのバリエーションは膨大になり、頭の中でイメージすることは不可能になります。

このタスクは組み合わせ論に起因する可能性があります。どのような組み合わせが形成されるのか、そしてその形成のパターンをどのように見つけることができるのかを考えてみましょう。

1. 各ツリーは最上位ノード (ツリーの頂点) から始まります。その後、ツリーの深さが広がります。
2. 画面に示されているように、各ノードは新しい子ツリー (サブツリー) の始まりです。左側のサブツリーは緑色、右側は赤色です。それぞれに独自の頂点があります。

概念レベルで N = 6 のタスクの例を見てみましょう。計算関数を numOfUniqueTrees(n: Int)と呼びます。

この例では、6 つのノードが指定されています。そのうちの 1 つは、前述の原則に従ってツリーの頂点を形成し、残りの 5 つは残りです。

これから、残りのノードと対話します。これはさまざまな方法で実行できます。たとえば、5 つのノードすべてを使用して左側のサブツリーを形成するか、5 つすべてを右側のサブツリーに送信します。または、ノードを 2 つに分割し、左側に 2 つ、右側に 3 つ (下の画面を参照) することで、そのようなバリアントの数を制限できます。

結果numOfUniqueTrees(6)を達成するには、ノードを分散するためのすべてのバリアントを考慮する必要があります。それらを表に示します。

この表には、ノードの 6 つの異なる分布が示されています。各ディストリビューションごとに生成できる一意のツリーの数を見つけてそれらを合計すると、最終結果が得られます。

配布する一意のツリーの数を見つけるにはどうすればよいですか?

Left Nodes と Right Nodes (表の左と右の列) という 2 つのパラメータがあります。

結果は、 numOfUniqueTrees(leftNodes) * numOfUniqueTrees(rightNodes)と等しくなります。

なぜ？左側には X 個の固有の木があり、それぞれに対して、Y 個の固有の木のバリエーションを右側に配置できます。これらを乗算して結果を取得します。

それでは、最初の分布のバリエーションを調べてみましょう (左 5、右 0)

右側にはノードがないため、 numOfUniqueTrees(5) * numOfUniqueTrees(0) 。結果はnumOfUniqueTrees(5)です。これは、左側の一意のサブツリーと右側の定数の数です。

numOfUniqueTrees(5)を計算しています。

これで、最小の副問題ができました。大型の場合と同様に、それを使用して操作します。この段階では、DP タスクの特性、つまり最適な下部構造、再帰的な動作が明らかです。

1 つのノード (緑色のノード) が頂点に送信されます。残りの (4 つの) ノードを、以前のエクスペリエンス (4:0)、(3:1)、(2:2)、(1:3)、(0:4) と同様の方法で分散します。

最初の分布 (4:0) を計算します。前述の類推により、これはnumOfUniqueTrees(4) * numOfUniqueTrees(0) -> numOfUniqueTrees(4)に等しくなります。

numOfUniqueTrees(4)を計算しています。頂点にノードを割り当てると、残りは 3 つになります。

分布 (3:0)、(2:1)、(1:2)、(0:3)。

2 つのノードの場合、一意のバイナリ ツリーは 2 つだけ、1 つの場合は 1 つだけです。 3 つのノードに対して一意のバイナリ ツリーには 5 つのバリエーションがあることを以前に説明しました。

結果として、distributions(3:0)、(0:3) は 5、(2:1)、(1:2) に等しくなります。2 になります。5 + 2 + 2 + 5 を合計すると、14 になります。 .nu numOfUniqueTrees(4) = 14。

メモ化の経験に合わせて、変数メモに計算結果を入力してみましょう。 4 つのノードのバリエーションを見つける必要がある場合は、それらを再計算するのではなく、以前の経験を再利用します。

計算 (5:0) に戻りましょう。これは、分布 (4:0)、(3:1)、(2:2)、(1:3)、(0:4) の合計に等しいです。 (4:0) = 14 であることがわかります。メモに戻りましょう、(3:1) = 5、(2:2) = 4 (左の 2 つのバリエーション * 右の 2 つのバリエーション)、(1:3) = 5、(0:4) = 14。これらを合計すると、42、 numOfUniqueTrees(5) = 42 になります。

分布の合計に等しいnumOfUniqueTrees(6)の計算に戻りましょう。

(5:0) = 42、(4:1) = 14、(3:2) =10 (左 5 * 右 2)、(2:3) = 10、(1:4) = 14、(0: 5) = 42。これらを合計すると、132、 numOfUniqueTrees(5) = 132になります。

課題は解決しました！

結果: N = 6 の場合の解法で重複する部分問題に注目してください。単純な解法では、 numOfUniqueTrees(3)が 18 回呼び出されます (下の画面)。 N が増加すると、同じ計算の繰り返しがはるかに多くなります。

(左 5、右 0) と (左 0、右 5) の一意のツリーの数が同じであることを強調表示します。 1 つの場合のみ左側にあり、もう 1 つの場合は右側になります。これは、(左 4、右 1) および (左 1、右 4) にも機能します。

動的プログラミングのアプローチとしてのメモ化により、このような複雑なタスクのソリューションを最適化できるようになりました。

実装

class Solution { fun calculateTees(n: Int, memo:Array<Int?>): Int { var treesNum = 0 if(n < 1) return 0 if(n == 2) return 2 if(n == 1) return 1 if(memo[n]!=null) return memo[n]!! for (i in 1..n){ val leftSubTrees = calculateTees( i - 1, memo) val rightSubTrees = calculateTees(n - i, memo) treesNum += if(leftSubTrees>0 && rightSubTrees>0){ leftSubTrees*rightSubTrees } else leftSubTrees+leftSubTrees } memo[n] = treesNum return treesNum } } 

結論

場合によっては、動的プログラミングを使用してタスクを解決すると、膨大な時間を節約し、アルゴリズムを最大限の効率で機能させることができます。

最後まで読んでいただきありがとうございます。ご質問に喜んでお答えいたします。