動的プログラミング: 概要、仕組み、および学習リソース

動的計画法は、数学者であり経済学者でもあるリチャード・ベルマンによって開発された概念です。

当時、ベルマンは複雑な最適化問題を解決する方法を探していました。 最適化問題では、一連のオプションから最適なソリューションを選択する必要があります。

最適化問題の例として、巡回セールスマン問題があります。 目標は、セールスマンが各都市を 1 回だけ訪問し、最初の都市に戻ることができるようにするための最短ルートを見つけることです。

これらの問題に対するベルマンのアプローチは、それらを小さなサブ問題に分割し、サブ問題を最小から最大に解決することでした。 次に、サブ問題の結果を保存し、それらを再利用してより大きなサブ問題を解決しました。 これが動的計画法の背後にある主な考え方です。

動的計画法とは

動的計画法は、最適化の問題を小さなサブ問題に分割し、各サブ問題を 1 回解決し、再利用して組み合わせて大きな問題を解決できるように、その解決策を保存することで解決します。 問題は最小から最大まで解決され、ソリューションの再利用が可能になります。

動的計画法のしくみ

動的計画法を使用して問題を解決するには、次の手順が必要です。

1. サブ問題を定義する: 大きな問題は小さなサブ問題に分割されます。
2. サブ問題を解決する : これには、特定されたサブ問題を解決することが含まれます。これは、再帰または反復を使用して行うことができます。
3. ソリューションの保存 : サブ問題のソリューションが保存されるため、再利用できます。
4. 元の問題の解を構築する: 大きな問題の解は、既に計算されたサブ問題から構築されます。

これを実際に確認するために、このプロセスを使用して 6 番目のフィボナッチ数 F(6) を計算します。

まず、解決する必要があるサブ問題を定義します。

F(n) = F(n-1) + F(n-2) for n > 1

したがって、F(6) = F(5) + F(4)

F(5) = F(4) + F(3)

F(4) = F(3) + F(2)

F(3) = F(2) + F(1)

F(2) = F(1) + F(0)

F(1) = 1

F(0) = 0

2 番目のステップでは、再帰関数または反復プロセスを使用して各サブ問題を解決します。 小さなサブ問題からの結果を再利用して、サブ問題を最小から最大まで解決します。 これにより、次のことがわかります。

F(0) = 0

F(1) = 1

F(2) = F(1) + F(0) = 1 + 0 = 1

F(3) = F(2) + F(1) = 1 + 1 = 2

F(4) = F(3) + F(2) = 2 + 1 = 3

F(5) = F(4) + F(3) = 3 + 2 = 5

F(6) = F(5) + F(4) = 5 + 3 = 8

各サブ問題を解決するとき、次のように、より大きなサブ問題を解決する際に再利用できるように、ソリューションを配列またはテーブルに保存します。

すべての副問題が解決されたら、その解決策を使用して元の問題の解決策を構築します。

この場合、元の問題の解は 6 番目のフィボナッチ数であり、最大の問題から特定されたサブ問題である F(5) と F(4) の結果を合計することによって求められます。 結果は 8 です。

動的計画法が使用される場所と理由

動的計画法は、小さなサブ問題に分割できる問題がある分野で使用され、その解決策はより大きな問題を解決するために使用されます。

これらの分野には、コンピューター サイエンス、経済学、数学、工学が含まれます。 コンピューター サイエンスでは、シーケンス、グラフ、整数値を含む問題や、競争力のあるプログラミングで問題を解決するために使用されます。

経済学では、金融、生産、およびリソース割り当ての最適化問題を解決するために使用されます。 数学では、動的計画法はゲーム理論、統計、確率で使用され、最適化問題を解決するために使用されます。

エンジニアリングでは、リソース割り当て、スケジューリング、製造、通信、および制御システムの問題を解決するために使用されます。

動的計画法を使用して最適化問題を解決することには、いくつかの利点があります。

1. 効率: 動的計画法は、類似の問題を何度も再計算する必要がないため、他の最適化アルゴリズムよりも効率的です。
2. 大規模な問題の解決: 動的計画法は、他の方法では解決できない大規模な最適化問題に最適です。 これは、問題をより小さな問題に分割して複雑さを軽減するためです。
3. 最適解: サブ問題と目的が正しく定義されている場合、動的計画法アルゴリズムは問題の最適解を見つけることができます。
4. シンプルさ:動的計画法アルゴリズムは、特に問題を特定の順序で定義できる場合、実装と理解が簡単です。
5. 拡張性:動的プログラミング アルゴリズムは、サブ問題を追加し、問題の目的を変更することで、より複雑な問題を解決するように簡単に拡張できます。

最適化問題を解決する場合、動的計画法はソリューションの効率を確保するための非常に便利なツールです。

動的計画法で使用されるアプローチ

動的計画法では、最適化問題を解決するために 2 つのアプローチが使用されます。 それがトップダウンアプローチとボトムアップアプローチです。

トップダウンアプローチ

このアプローチはメモ化とも呼ばれます。 メモ化は、関数呼び出しの結果をキャッシュに保存し、キャッシュされた結果を再度計算するのではなく、次に必要なときに返すことによって、コンピューター プログラムを高速化するために主に使用される最適化手法です。

トップダウンのアプローチには、再帰とキャッシングが含まれます。 再帰には、問題のより単純なバージョンを引数として自分自身を呼び出す関数が含まれます。 再帰は、問題をより小さなサブ問題に分解し、サブ問題を解決するために使用されます。

サブ問題が解決されると、その結果がキャッシュされ、同様の問題が発生するたびに再利用されます。 トップダウンは理解と実装が容易で、下位の問題を 1 回だけ解決します。 ただし、再帰のために多くのメモリを消費するという欠点があります。 これにより、スタック オーバーフロー エラーが発生する可能性があります。

ボトムアップアプローチ

タビュレーションとも呼ばれるボトムアップ アプローチは、再帰を排除して反復に置き換えることで、スタック オーバーフロー エラーを回避します。

このアプローチでは、大きな問題を小さなサブ問題に分割し、サブ問題の解決策を使用して大きな問題を解決します。

小さいサブ問題は、最初に最大のものから最小のものへと解決され、その結果は行列、配列、またはテーブルに格納されるため、集計と呼ばれます。

保存された結果は、サブ問題に依存するより大きな問題を解決します。 元の問題の結果は、以前に計算された値を使用して最大のサブ問題を解決することによって検出されます。

このアプローチには、再帰を排除することでメモリと時間を効率的に使用できるという利点があります。

動的計画法で解ける問題の例

以下は、動的計画法を使用して解決できるプログラミングの問題の一部です。

＃1。 ナップザック問題

ナップザックは、キャンバス、ナイロン、または革で作られたバッグで、通常は背中にストラップが付けられ、兵士やハイカーが物資を運ぶために使用します.

ナップザック問題では、ナップザックが提示され、その運搬能力を考慮して、それぞれに価値のあるアイテムを選択する必要があります。 アイテムの最大合計値を取得し、アイテムの重量がナップザックの容量以下になるように選択する必要があります。

ナップザック問題の例を以下に示します。

ハイキング旅行に行く予定で、容量が 15 キログラムのナップザックを持っていると想像してください。 下の表に示すように、持ち込めるアイテムのリストとその値と重量があります。

総重量がナップザックの容量 (15 キログラム) 以下でありながら、アイテムの合計値が最大になるように、持ち込むアイテムのサブセットを選択します。

ナップザック問題の現実世界への適用には、ポートフォリオに追加する証券を選択して、リスクを最小化し、利益を最大化し、原材料を削減する最も無駄のない方法を見つけることが含まれます。

＃2。 スケジューリングの問題

スケジューリング問題は、タスクを一連のリソースに最適に割り当てることを目標とする最適化問題です。 リソースは、タスクを完了するために使用されるマシン、人員、またはその他のリソースです。

スケジューリングの問題の例を以下に示します。

あなたがプロジェクト マネージャーで、従業員のチームが完了する必要がある一連のタスクのスケジューリングを担当しているとします。 各タスクには、開始時刻、終了時刻、およびそのタスクを完了する資格のある従業員のリストがあります。

タスクとその特性を説明した表を次に示します。

各タスクを従業員に割り当てて、合計完了時間を最小限に抑えます。

スケジューリングの問題は、機械、材料、ツール、および労働力などのリソースの割り当てを最適化しようとするときに、製造業で発生する可能性があります。

また、ベッド、人員、および医療用品の使用を最適化するときに、ヘルスケアで発生する可能性があります。 この問題が発生する可能性がある他の業界は、プロジェクト管理、サプライ チェーン管理、および教育です。

＃3。 巡回セールスマン問題

これは、動的計画法を使用して解決できる、最も研究されている最適化問題の 1 つです。

巡回セールスマン問題は、都市のリストと、都市の各ペア間の距離を提供します。 各都市を 1 回だけ訪れ、元の都市に戻る最短ルートを見つける必要があります。

巡回セールスマンの問題の例を以下に示します。

あなたが最短時間で一連の都市を訪問する必要がある営業担当者であると想像してください。 次の表に示すように、訪問する必要がある都市のリストと、都市の各ペア間の距離があります。

巡回セールスマン問題は、観光客向けのルートを計画する際のレジャー業界、商品の出荷を計画する際のロジスティクス、バスのルートを計画する際の輸送、および販売業界などで発生する可能性があります。

明らかに、動的計画法には多くの実世界のアプリケーションがあり、それについてさらに学ぶのに役立ちます。

動的計画法の知識を深めるために、次のリソースを検討してください。

資力

リチャード・ベルマンによる動的プログラミング

動的プログラミングは、動的プログラミングを思いつき、初期段階で開発した Richard Bellman による本です。

プレビュー	製品	評価	価格
	Dynamic Programming (Dover Books on Computer Science)	評価はまだありません	$17.29	アマゾンで購入

この本は、テキストを理解するために必要な数学と微積分の基礎知識だけを必要とする、理解しやすい方法で書かれています。 この本の中でベルマンは、動的計画法の鍵となる多段階決定プロセスの数学的理論を紹介しています。

次に、この本では、多段階の生産プロセスにおけるボトルネックの問題、存在定理と一意性定理、および最適な在庫方程式を調べます。

本書の最も優れた点は、Bellman がロジスティクス、スケジューリング理論、通信理論、数理経済学、制御プロセスなどの分野における多くの複雑な問題の例を提供し、動的計画法がどのように問題を解決できるかを示していることです。

この本は、Kindle、ハードカバー、およびペーパーバックのバージョンで入手できます。

動的計画法アルゴリズムマスターコース

この Udemy による動的プログラミング アルゴリズム マスター コースは、Google のソフトウェア エンジニアである Apaar Kamal と、Google で働いていた Prateek Narang によって提供されています。

このコースは、学習者が動的プログラミングを必要とする多くの問題を特徴とするプログラミング競技で優れた成績を収められるように最適化されています。

プログラミングの競技者は別として、このコースは、アルゴリズムの理解を深めようとしているプログラマーや、プログラミングの面接やオンライン コーディング ラウンドの準備をしている人々にとって理想的です。

コースの長さは 40 時間以上で、動的プログラミングについて詳しく説明します。 このコースでは、最初に再帰やバックトラッキングなどの概念を復習します。

次に、ゲーム理論における動的プログラミング、文字列、ツリーとグラフ、行列累乗、ビットマスク、組み合わせ論とサブシーケンス、分割問題、多次元動的プログラミングなど、他の多くの概念について説明します。

競技プログラミングの基礎、マスターアルゴリズム

Udemy では、Prateek Narang と Amal Kamaar による Competitive Programming Essentials Course を提供しています。このコースでは、動的プログラミング、数学、数論、高度なデータ構造とアルゴリズムを、競争力のあるプログラマーにとって有用かつ適切な方法でカバーしています。

このコースでは、競争力のあるプログラミングで役立つより複雑なアルゴリズムとテクニックに飛び込む前に、データ構造とアルゴリズムの復習を行います。

このコースでは、動的プログラミング、数学、ゲーム理論、パターン マッチング、ビットマスキング、およびプログラミング コンテストで使用およびテストされた無数の高度なアルゴリズムについて説明します。

Udemy コースは 10 のモジュールと 42 のセクションに分かれており、各セクションの後に多くの練習問題が用意されています。 このベストセラー コースは、競技プログラミングに関心のあるすべての人にとって必携のコースです。

最後の言葉

動的プログラミングは、プログラマーが現実世界の問題解決能力を向上させるために学ぶ有益なスキルです。 したがって、プログラマーは、推奨されるリソースを調べて、この重要なツールをツールボックスに追加することを検討する必要があります。

次に、データ サイエンスで使用するプログラミング言語を確認できます。