動的プログラミングという用語は、この分野に長く携わっていれば、おそらく今ではよく使われる用語です。 このトピックは、設計レビュー会議やエンジニアの日常のやり取りで頻繁に話題になり、技術面接でも焦点となります。 分割統治戦略は、あらゆる目標を達成するための確実な方法です。 コンピューター プログラミングでも、これと同じ考えが当てはまります。 多くの問題にはサブタイプがあり、それらを分離して個別に処理できるため、主要な問題の最終的な解決が可能になります。 この記事では、動的プログラミング アルゴリズムと Python について説明します。
動的プログラミングとは何ですか?
動的プログラミングは、最初に複雑な問題をより単純なものに落とし込み、次にそれらの単純な問題の解決策を元の問題を解決するための構成要素として使用することによって、複雑な問題を解決する方法です。
当面の問題を管理可能な部分に分割します。 ほとんどの場合、親の問題とその子の問題の唯一の本当の違いは、それらの相対的な大きさです。 したがって、これらの小さな問題は、さらに多くの小さな問題に分割することができ、これを無限に繰り返すことができます。 問題とそのさまざまなサブ問題がツリーを形成していると想像してください。 最初に「リーフ」問題に取り組み、次にその「親」問題に取り組み、というように問題ツリーを上っていきます。 小さな困難に取り組むときは、後で使用できるように進捗状況を記録します。 これにより、今後、問題のその部分をスキップすることができます。
この方法は、問題を独立して解決できる小さな問題に分割し、結合して最終的な解決策を得るという点で、分割統治手法に似ています。
動的プログラミングはどのように機能するのでしょうか?
動的プログラミングは、難しい問題を構成要素に分解することで単純化するため、効果的です。 次のステップは、これらの今後の課題に対する最善の答えを正確に特定することです。 これらの手順の結果を記憶できるため、対応する解をストレージから取得して、さらなる計算を行わずに使用できます。 また、以前に解決した部分問題の再計算を避けるために、解を保存することもできます。
動的プログラミングを実行するには、次の XNUMX つの方法があります。
#1. トップダウンアプローチ
コンピューター サイエンスでは、通常、問題は、解決策を再帰的に構築するか、前のステップの結果を使用して目前の問題に取り組むことによって解決されます。 サブ問題が類似している場合、サブ問題の解決策を記憶したり、表に記録したりすることが可能です。 トップダウン方式は暗記による学習に基づいています。 メモ化は、再帰とキャッシュを XNUMX 回実行することと同じです。 再帰には関数への間接的な呼び出しが含まれますが、キャッシュには中間結果の追跡が含まれます。
トップダウン アプローチには次のような多くの利点があります。
- トップダウン方式は理解しやすく、適用しやすいです。 何を行う必要があるかをよりよく理解するために、このメソッドは問題を構成要素に分解します。 新たな開発が行われるたびに、以前は乗り越えられなかった障害が解放されます。 一部の部分は他の問題にも適用できる可能性があります。
- これにより、オンデマンドでサブ問題の解決が可能になります。 トップダウンの方法では、問題を管理可能なチャンクに分解し、それらのチャンクに対する解決策を後で使用できるように保存することができます。 その後、顧客は各コンポーネントを修正するための支援を求めることができます。
- デバッグも簡素化されます。 問題を小さな部分に分割すると、答えを追跡し、潜在的な間違いを確認しやすくなります。
トップダウン アプローチを使用する場合の欠点の一部を次に示します。
- トップダウン戦略では再帰メソッドが使用されますが、これは他のアプローチよりもコール スタック内でより多くのメモリを消費します。 これは最終的にパフォーマンスの低下につながります。 さらに、再帰が過去に遡りすぎると、スタック オーバーフローが発生する可能性があります。
#2. ボトムアップアプローチ
問題の解決策がそれ自体をループバックする形でサブ問題の観点から表現された後、ユーザーはボトムアップのアプローチを使用して問題を書き直すことができます。このアプローチでは、最初に小さなサブ問題を解決してから、その解決策をより大きなサブ問題に適用します。 。
トップダウン方式とは対照的に、ボトムアップ方式を使用すると再帰が排除されます。 したがって、再帰関数によって不要なオーバーヘッドが追加されたり、スタックがオーバーフローしたりすることはありません。 さらに、データ圧縮も可能になります。 同じ値を再計算する必要がなくなることで、再帰の時間的な複雑さが軽減されます。
ゼロから取り組むことの利点は次のとおりです。
- まず、より小さな再利用可能な部分問題から巨大な問題をどのように構築するかを決定します。
- 再帰を排除することで、利用可能なメモリをより有効に活用できます。 副作用として、タイミングの複雑さが軽減されます。
動的計画法の特徴
動的プログラミングには、次の XNUMX つの際立った特性があります。
#1. サブ問題の重複
主要な問題をより管理しやすく変更したものは、「サブ問題」と呼ばれます。 フィボナッチ数列。各数値は、前の 0 つの数値の合計に等しくなります (1、1、2、3、5、8、XNUMX、…)。 フィボナッチ数列の n 番目の値を見つけるタスクを、より管理しやすいチャンクに分割できます。 同じ部分問題に何度も取り組んで解決策を見つけるにつれて、これらの重複する一連の困難を解決するのはますます困難になります。
動的プログラミングを使用すると、重複する部分問題が普遍的に発生するため、大規模なプログラミング ジョブを管理可能なチャンクに分割できます。
#2. 下部構造は最適な特性を持っています
最適部分構造の性質は、すべての部分問題の解から最適解を作成できる場合に現れます。 再帰を機能させるには、それぞれの重複から導き出した答えを問題全体に適用する必要があります。 フィボナッチ数列の場合のように、各部分問題に、その値を決定するためにシーケンス内の次の部分問題に適用できる解がある場合、最適な部分構造のプロパティが問題全体によって表示されます。
現実世界での動的プログラミングの使用
ここでは動的プログラミングの使用法を示します。
#1. ナップサック問題
動的プログラミングは、ナップザック問題を解決するために広く使用されてきました。 私たちが直面している問題は次のとおりです。
各サブ問題の理想的な値は、問題のアイテムの数とナップザックに残っているスペースの量によって決まり、XNUMX 次元配列に格納できるため、この問題を迅速に解決できます。 各段階で現在の項目を含めたり除外したりすることで、価値を最大化できます。 答えは配列の右下隅にあります。
ナップザック問題は、荷物の梱包から投資の決定、リソースの割り当てに至るまで、さまざまな状況で使用できます。
#2. すべてのペアの最短パス
重み付きグラフにおける最短経路の問題は、動的プログラミングのもう XNUMX つの典型的な使用法です。 フロイド・ウォーシャルやベルマン・フォードなどの手法を使用すると、任意の XNUMX つのノードのペア間の最短パスを見つけることができます。
任意の XNUMX つのノード間の最短パスを追跡するために、これらのアルゴリズムでは XNUMX 次元配列が使用されます。 また、開始点からの距離を追跡するために、結果を各段階の開始点と中間ノード間の距離と比較します。 結局のところ、反復が完了すると、最終的な解は距離行列になります。
全ペア最短経路の問題を解決するには、ネットワーク分析、ルーティング、ナビゲーション、ソーシャル ネットワーク分析など、いくつかの用途があります。
#3. シームカービング
画像処理の分野では、シーム カービングは動的プログラミングの興味深い応用例です。 ここでの課題は、画像の重要な特性を一切変更せずに画像のサイズを縮小することです。 シームと呼ばれる画像内の低エネルギー ルートを使用してピクセルを減算または追加して、この効果を実現できます。
動的プログラミングを使用すると、勾配と近傍に基づいて画像内の各ピクセルの累積エネルギーを計算し、その情報を利用してどの継ぎ目を削除または追加するかを決定できます。 次に、画像の下から上に向かって作業することで、位置エネルギーが最小の継ぎ目を見つけることができます。 この方法は、必要なサイズに達するまで繰り返し使用できます。
さらに、シームカービングを利用して、画像のサイズ変更、トリミング、ターゲット変更などを行うことができます。
#4. 機械学習とゲノミクス
配列アライメント、隠れマルコフ モデル、系統樹などの機械学習とゲノミクスの課題はすべて、動的プログラミングの問題解決能力に適しています。
共通点を明らかにするために複数のシンボル配列 (多くの場合は DNA またはタンパク質) を整列させることを配列アラインメントと呼びます。 これにより、それらの進化のつながり、社会における機能、構造的特徴が明らかになります。 配列間の一致および不一致にスコアを割り当てることにより、動的プログラミングによって最適なアライメントを見つけることができます。
隠れマルコフ モデルとして知られる確率モデルは、未知の状態を条件とする時系列データを記述するために使用されます。 これらは、音声認識、NLP、バイオインフォマティクスなどの難しい現象をモデル化するのに役立ちます。一連の観察結果が与えられると、ビタビや前方後退などの動的プログラミング技術を使用して、最も可能性の高い隠れ状態のシーケンスを決定できます。
系統樹は、種または遺伝子間の関係を時間の経過とともに示します。 これらの共通点から、共通の祖先、分岐の日付、進化の出来事を推測することが可能です。 また、Fitch や Sankoff のような動的プログラミング アルゴリズムを使用して、シーケンス データを使用して最適な系統樹を生成することもできます。
＃5。 暗号化
秘密通信の研究である暗号学も、動的プログラミングの問題解決能力の恩恵を受けています。 暗号化、復号化、デジタル署名、認証、およびその他の同様のプロセスはすべて暗号化の一部です。
暗号化により、情報は人間が判読できる情報から秘密鍵が判読できる情報に変換されます。 復号化は、元のキーまたは新しいキーを使用して、暗号化されたデータを平文に変換するプロセスです。 デジタル署名を使用すると、メッセージまたはドキュメントの信頼性と完全性を検証できます。 送信者または受信者の資格情報を確認することで、送信者または受信者の身元を確認できます。
動的キー暗号化、コードベースの暗号化、動的プログラミングベースの暗号化など、さまざまな種類の暗号化はすべて動的プログラミングで実装できます。
動的キー暗号化は、常に変更されるキーを使用してメッセージを暗号化および復号化するメカニズムです。 「動的」キーは、時間の経過とともに、または他の要因に応じて進化するキーです。 これにより、攻撃に対して脆弱な静的キーよりも安全になります。 動的キー暗号化を実装する場合、動的プログラミングを使用してキーを生成し、最新の状態に保つことができます。
コードベースの暗号化として知られる技術を使用すると、その過程でエラー訂正コードを使用してメッセージを暗号化および復号化することができます。 誤り訂正符号を使用して伝送障害を修正することが可能です。 コードベースの暗号化の使用は、量子コンピューターからの攻撃に対して安全であるため、耐量子性があると広く考えられています。 動的プログラミングを使用すると、コードベースの暗号システムを使用して通信を暗号化および解読できます。
データの暗号化および復号化の方法として、動的計画ベースの暗号化は動的計画アルゴリズムに依存します。 最適化の課題に取り組むために、動的プログラミング手法は通常、問題をより単純な部分問題のセットに分割します。 動的プログラミング暗号化では、ナップザック、最短パス、シーム カービングが使用されます。
動的プログラミングの実例とは何ですか?
実際のソフトウェア アプリケーションの多くのインスタンスは、ホスト システム上のリソース フットプリントを削減しながら、俊敏性と効率性を維持するために動的プログラミングを使用しています。 いくつかの例は次のとおりです。
- グーグルマップ。 Google マップは動的プログラミングを使用して、特定の出発地から複数の異なる目的地までの最速ルートを検索します。
- ネットワーキング。 単一の送信者から複数の受信者への順次データ転送。
- スペルチェッカー。 編集距離アルゴリズムは、ある単語を別の単語に変換するために必要なステップ数を決定し、XNUMX つの単語間の非類似度の定量的な尺度を提供します。
- 盗作ソフトウェア。 文書距離法は、テキスト文書の類似性を判断するのに役立ちます。
- サーチエンジン。 XNUMX つのインターネット コンテンツが実際にどの程度類似しているかを判断するため。
動的プログラミングの問題を解決するには?
動的計画法の問題を解決するための公式を学ぶことは、動的計画法の概念を理解した後の次のステップです。 ここでは、動的プログラミングを当面の問題に適用し、実行可能な解決策に到達する方法について、いくつかの提案を示します。
#1. 動的プログラミングの問題を認識する
最も重要な部分は、動的計画アルゴリズムが指定された問題ステートメントを解決できることを理解することです。 この問題を解決するには、まず、各問題ステートメントを関数として小さな部分に分割できるかどうかを判断する必要があります。
#2. 問題の原因を特定する
動的プログラミングがこの仕事に適したツールであるとすでに結論付けている場合、次のステップは、問題を構成する部分問題の中から問題の再帰構造を特定することです。 この場合、問題の状態の流動的な性質を考慮する必要があります。 この変数は、配列の位置または問題解決速度である可能性があります。
さらに、問題の構成要素を数えることも重要です。
#3. 反復的方法と再帰的方法のどちらかを選択してください
動的プログラミングの問題を解決するには、反復的または再帰的アプローチを利用できます。 これまでの説明から、再帰的方法が好ましいと言っても過言ではありません。 ただし、問題を解決するために選択された方法に関係なく、前述の考慮事項はすべて独立して成立します。
再帰的アプローチと反復的アプローチの両方で、再帰関係と問題の基本ケースを指定する必要があります。
#4. 暗記システムを組み込む
同様の構造の問題に取り組むときは、同等のサブ問題を処理した過去の経験を思い出すと役立つ場合があります。 この結果、問題の時間計算量は減少します。 暗記せずに同じ部分問題を何度も繰り返し解決し続けると、タスクの時間の複雑さが指数関数的に増大する可能性があります。
#5. 再帰関係を言葉で表現する
問題を解決するとき、多くのプログラマーは漸化関係の定義をスキップして、そのままコーディングに取り掛かります。 開始する前に繰り返し関係を明示的に表現できれば、問題をよりよく把握でき、より迅速にコーディングできるようになります。
アルゴリズム動的プログラミング
動的プログラミングのほとんどのアプリケーションには再帰アルゴリズムが含まれています。 最適化に動的プログラミングを使用するということは、最適化の問題の大部分に再帰が本質的に含まれていることを意味します。
ただし、動的プログラミングですべての再帰的な問題を解決することはできません。 フィボナッチ数列問題のように、重複する部分問題が存在しない限り、再帰では分割統治戦略によってのみ解を見つけることができます。
これは、マージ ソートのような再帰的アルゴリズムの根底にある部分問題が重複しないため、動的プログラミングの使用が除外されるためです。
さまざまな種類の動的プログラミング アルゴリズム
ここでは、さまざまな種類の動的プログラミング アルゴリズムを示します。
#1. 最長共通部分列
最長共通部分列 (LCS) の要素は、元のシーケンス内で任意の順序で出現する可能性があります。 LCS は、指定されたすべてのシーケンスに共通する最長のサブシーケンスとして定義されます。
1 つのシーケンス S2 と S1 が提供される場合、S2 と S1 の両方のサブシーケンスであるシーケンス Z は、それらの共通サブシーケンスと呼ばれます。 追加の要件として、Z はセット S2 および SXNUMX のインデックスの厳密に昇順のシーケンスで構成されている必要があります。
上昇シーケンスを形成するには、Z 内の選択された要素のインデックスが厳密に増加する必要があります。
#2. フロイド・ウォーシャルアルゴリズム
重み付けされたグラフ内の頂点のすべてのペア間の最短経路を見つけることが、フロイド・ウォーシャル アルゴリズムの目標です。 このメソッドは、両方向の重みを使用してチャートを処理します。 一方、エッジの合計が負であるサイクルでは失敗します。
フロイドのアルゴリズム、ロイ-フロイド アルゴリズム、ロイ-ウォーシャル アルゴリズム、および WFI アルゴリズムはすべて、フロイド-ウォーシャル アルゴリズムの名前です。
このアルゴリズムは動的プログラミング手法を使用して、最適なショートカットを見つけます。
動的プログラミング アルゴリズムはどのようにして再帰的手法よりも速く Lcs 問題を解決するのでしょうか?
動的プログラミングにより、関数呼び出しのオーバーヘッドが軽減されます。 各関数呼び出しの結果を記憶するため、後続の呼び出しでは同じ作業を繰り返すことなく、保存されたデータを利用できます。
X の要素が Y の要素と比較されるたびに、結果はテーブルに書き込まれ、前述の動的プロセスの後続の計算で使用できるようになります。
したがって、動的メソッドの実行時間は、テーブルを埋めるのに必要な時間 (O(mn)) と同じになります。 対照的に、再帰的アルゴリズムの複雑さは 2max(m, n) です。 また、読んでください ビジネス ニーズに適した暗号化アルゴリズムの種類を選択する方法
Python の動的プログラミングの問題とは何ですか
動的プログラミングを利用すると、任意の数の異なる問題ステートメントに対する最適な解決策を決定できます。 以下では、最も頻繁にリクエストされる有名な問題ステートメントのいくつかを取り上げ、適切な Python コードとともに簡単な説明を提供します。
#1. ナップサック (0-1) 有界
この状況では、N 個の商品の価格と重量が与えられ、それらを容量 W のバックパックに詰めるという任務が与えられます。 目標は、すべてをナップザックに入れながら、選択するアイテムの数を最小限に抑えることです。
物販組織の技術面接のほとんどでは、動的プログラミング手法の典型的な例であるナップザック問題を解くことが候補者に求められます。
問題の説明 容量 W のバッグと、それぞれの重さとそれに対応する利益を持つ物のリストがあると仮定します。 目標は、効果的な不良充填により収益を最大化することです。
答えは、1 から W までの考えられる各重みの列と、実際に選択した重みの行を含むテーブルを作成することです。 このテーブルは dp[][] として知られることになります。 「j」がナップザックの容量で、重量/アイテム配列の最初の「i」要素が含まれている場合、テーブル内の状態 /cell dp[i][j] は可能な限り最高の利益を示します。
その結果、最後のセルの値が解を示します。 ナップザックの重量制限を超えないものだけを詰めることが重要です。 すべての列を埋めることができる基準「weight>wt[i-1]」の代替案が XNUMX つあります。
#2. 0/1 ナップザック境界メモ化
重量と収益が既知のアイテム (サイズ K) をバッグに詰めます。あなたの目標は、収益を最大化することです。 ここでは、表作成の代わりにメモ化を使用して、問題を解決できるかどうかを確認します。
上記の 0/1 ナップザック問題は、解を見つけるためにボトムアップ戦略を使用しましたが、この問題は解を得るために暗記に基づくトップダウン アプローチを使用します。
動的プログラミングでは、暗記を利用して、問題の同じ部分を何度も解く必要性を減らします。 これにより、サブ問題を常に解決する必要がなくなり、出力を生成するプロセスが合理化されます。
問題の説明 容量 W のバッグと、それぞれの重さとそれに対応する利益を持つ物のリストがあると仮定します。 可能な限り効率よくバッグがいっぱいになれば、潜在的に最高レベルの利益を得ることができます。
解決策は、最初に 1 次元配列を構築して、個々の部分問題に対する最終的な答えを保持することです。 テーブルの列には、XNUMX から W までのすべての潜在的な重みがリストされ、多数のセクションに分割され、行には指定された時点で選択した重みが表示されます。
dp 配列を使用して、解決された各部分問題を追跡します。 以前に解決した部分問題を解決するのではなく、その答えを返すだけです。
#3. 等しいサブセット問題
動的プログラミングを使用して、両方のサブセット内の項目の合計が同じになるような、指定されたセットのパーティションを見つけて、サブセットが等しい問題を解決します。 他の名前に加えて、均等サブセット問題 (または分割問題) は、動的プログラミングの力を示す主な例です。
ここでのタスクでは、後続の各サブセットの全体サイズが同じになるように、配列 arr を半分に分割する必要があります。
解決策として、(sum/2+1)*(target+1) の次元を持つ XNUMX 次元配列を構築する必要があります。 ここでは、元の配列を分割した結果をサブセットごとおよび合計ごとに保存し、後で取得することができます。 配列の最初の次元は作成できるさまざまなサブセットを表し、配列の XNUMX 番目の次元はサブセットを結合することで計算できるさまざまな合計を表します。
動的プログラミングの利点
動的プログラミングの利点をいくつか紹介します。
#1. 効果的な治療法
動的プログラミングは、最適な部分構造と重複する部分問題を持つ問題に対する最適な解決策を見つけるための強力なツールです。 それらを管理可能な部分に分解することで、このメソッドを使用してこれらの課題に取り組みやすくなります。 動的プログラミングでは、反復計算を回避し、部分問題に対する答えを再利用することで、最適な解を作成できます。
#2. 問題の発見が容易になる
難しい問題を最初に単純な部分に分解すると、解決が容易になります。 複雑な問題をより管理しやすいチャンクに分割することで、複雑な問題への取り組みが容易になります。 この方法により、解決策が簡素化され、問題に取り組みやすくなります。
＃3。 効率的
動的プログラミングは、不必要な計算を排除し、以前に解決した部分問題を再利用することにより、問題の解決に必要な時間を大幅に短縮できます。 副次的な問題が重なっている場合、この方法は問題を解決するために必要な対策の総数を減らすのに役立ちます。
#4. 問題に複数の解決策がある場合に効果的
動的プログラミングは、考えられるいくつかの説明のうちどれが当てはまる可能性が高いかを判断するのに役立ちます。 問題を解決するための実行可能なオプションが複数ある場合、この方法は最適なオプションを絞り込むのに役立ちます。
動的プログラミングの欠点は何ですか?
動的プログラミングの欠点をいくつか紹介します。
#1. 繰り返し起こるサブ問題
動的プログラミングは、問題に重複する下位問題がある場合に最も効果的に機能しますが、常にそうであるとは限りません。 個々の問題が交差していなければ、それは機能せず、おそらく最適な解決策も提供されないでしょう。
#2. 時間と空間の複雑さ
問題が大きい場合、動的プログラミングは大量のメモリと記憶域を必要とする可能性があり、解決策の時間と空間の複雑さが増大します。 このアプローチではメモリを使用して、中間結果をテーブルまたはメモ化テーブルに保存します。
#3. 問題の枠組み
動的プログラミングは、特定の問題構造に対しては効果的ですが、常に最良の選択であるとは限りません。 この方法は、問題に重複するサブ問題がある場合に最も効果的であるため、他の状況には適用できない場合があります。
#4. 実践するのが難しい
動的プログラミングはアルゴリズムとデータ構造に関する深い知識を必要とするため、初心者にとって実装は困難です。 この方法では、事前の検討と当面の問題についての深い知識が必要です。
ボトムライン
結論として、動的プログラミングは答えを見つけるための効果的な方法ですが、他のアプローチの方が望ましいと言えます。 メリットとデメリットを理解し、当面の問題に応じて適切な方法を選択することが重要です。 最適な部分構造と重複する部分問題を持つ問題の場合、動的プログラミングは最適な解決策を導き出すことができます。 ただし、この方法が常に適用できるとは限りません。
開発が難しく、多くのメモリを使用しますが、問題解決プロセスを合理化し、計算時間を短縮できるため、コンピューター科学者や数学者にとって重要なリソースとなります。
動的プログラミングに関するよくある質問
線形計画法と動的計画法の違いは何ですか?
線形最適化問題には、線形計画法 (LP) アルゴリズムがあり、非凸制約を伴う一般的な非線形最適化問題には、解の大域的最適性を保証する動的計画法 (DP) があります。
動的プログラミングを学ぶのはどれくらい難しいですか?
動的プログラミングが、特にコンピューター サイエンスの分野の初心者にとって、複雑な主題であることは周知の事実です。 ただし、基本原則をしっかりと理解し、十分な練習をすれば、動的プログラミングを簡単に学ぶことができます。
動的プログラミングは非常に難しいですか?
大変だよ！ まず、動的プログラミング手法の概念を理解するのは難しいかもしれません。 熟練プログラマーなら誰でも、DP を習得するには多大な時間を費やす必要があると証言するでしょう。 問題を構成要素に分解し、実行可能な全体に再組み立てするスキルも必要です。
同様の記事
- プロジェクトの時間管理：効果的な管理のためのプロセス、ツール、ソフトウェア
- Amazon SEO: 商品を最適化してランクを上げる方法
- 最も人気のあるプログラミング言語: 2023 年ガイド
- コンピュータープログラミングとは: 例、種類、コース、ソフトウェア
- オンライン遺言: 最高のオンライン遺言作成者。
参照
