最近、動的計画法と貪欲法の復習をしました。GPT の助けを借りてまとめました。
動的計画法と貪欲法の違い#
一般的に、問題が最適な部分構造と重複する部分問題を持つ場合、動的計画法を使用することが考えられます。問題が最適な部分構造を持ち、局所的な最適解がグローバルな最適解（貪欲選択性）につながる場合、貪欲法を使用することが考えられます。問題が上記のすべての特性を満たす場合、動的計画法と貪欲法の両方を使用することができますが、具体的な選択は実際の問題の要件と制約に依存します。
- 重複する部分問題
動的計画法は通常、多くの重複する部分問題が存在する場合に使用されます。動的計画法では、一度問題の解を計算すると、その解を再計算する必要がある場合に直接使用するために保存します。一方、貪欲法は部分問題の重複を考慮しません。 - 最適な部分構造
動的計画法と貪欲法の両方には、問題が最適な部分構造の特性が必要です。これは、子問題の最適解から元の問題の最適解を得ることができることを意味します。 - 選択の特性
貪欲法は選択の特性に依存しており、局所的な最適選択がグローバルな最適解につながることを意味します。貪欲法では、各決定段階で現時点で最も良い選択を行い、その選択が将来の決定にどのような結果をもたらすかを考慮しません。一方、動的計画法では、すべての可能な選択肢を評価し、最適な選択肢を選びます。 - 問題の解決方法
貪欲法は通常、反復的な方法です。各ステップで現時点で最適な解を選択するだけで、以前のまたは将来の決定を考慮する必要はありません。一方、動的計画法では、すべての子問題の解決策を格納および検索するためにテーブルを作成する必要があります。
問題が動的計画法か貪欲法かを判断する方法#
- 問題が最適化問題かどうかを確認する
最短パス問題、最大利益問題など、これらの問題は動的計画法または貪欲法を使用する場合があります。 - "最適な部分構造" の特性が存在するかどうかを確認する
最適な部分構造は、問題の最適解がその部分問題の最適解から構成されることを意味します。このような構造が存在する場合、動的計画法または貪欲法を使用することが適している可能性があります。 - 動的計画法の場合、"重複する部分問題" が存在するかどうかを確認する
つまり、複数の問題が同じ部分問題を共有し、重複した計算が効率を低下させる可能性があります。このような場合、動的計画法が適しています。 - "貪欲選択性" が問題を満たしているかどうかを判断する
つまり、局所的な最適選択がグローバルな最適解につながることができるかどうかです。つまり、ステップバイステップで最適な選択をすることができ、全体を考慮する必要がない場合、貪欲法が適している可能性があります。 - 問題の複雑さと解決速度を考慮する
貪欲法は通常、より単純で計算速度も速いですが、常に最適解を見つけるわけではありません。一方、動的計画法はより複雑で計算速度も遅いかもしれませんが、問題の最適解を見つける可能性が高いです。 - 問題のスケールを考慮する
動的計画法は大規模な問題の場合、多くのメモリを使用して部分問題の解を保存する必要があるため、実行不可能な場合があります。
子問題をどのように分割するか？#
子問題を分割することは、動的計画法と貪欲法の問題を解決するための重要なステップです。
子問題を分割するには、練習と経験が必要です。異なる問題には異なる方法が必要な場合があり、学習には時間と忍耐が必要です。
- 最適な部分構造を特定する
より小さな、単純化されたバージョンまたはサブセットの問題を見つけようとしてください。このようなサブ問題の最適解は、元の問題の最適解の構築に役立ちます。 - 子問題の定義
子問題が何であるかを明確に定義する必要があります。たとえば、最短パス問題では、子問題は出発点から中間点までの最短パスかもしれません。 - 状態遷移方程式
この方程式は、子問題がどのように関連しているかを表します。状態遷移方程式は、既に解決された子問題の答えを使用して、現在の子問題の解を導出する方法を示します。 - 境界条件
解決が明らかな最も単純な子問題を見つけます。たとえば、フィボナッチ数列の問題では、最初の 2 つの数が境界条件です。 - 子問題間の関係
動的計画法では、子問題が重複することがよくあり、他の子問題を解決する際に再び現れることがあります。この場合、以前に解決された子問題の答えを使用して重複計算を避けることができます。
典型的な動的計画法の問題 5 つ#
-
- フィボナッチ数列：n が与えられた場合、フィボナッチ数列の第 n 項を計算する。
-
- 鋼の棒の切り分け：長さと価格のリストが与えられた場合、最大の総価値を得るためにどのように鋼の棒を切り分けるかを求める。
-
- 最長共通部分列：2 つの文字列が与えられた場合、最長の共通部分列を見つける。
-
- 0-1 ナップサック問題：一連のアイテムが与えられ、各アイテムには重量と価値があります。背負い袋の重量制限を超えないようにアイテムを選択する方法を決定し、総価値を最大化します。
-
- 行列の連鎖積：行列の連鎖が与えられた場合、最適な乗算順序を決定し、総乗算回数を最小化します。
典型的な貪欲法の問題 5 つ#
-
- 活動選択問題：一連の活動が与えられ、各活動には開始時間と終了時間があります。これらの活動の間に時間的な衝突がないように、最大数の活動を選択する必要があります。
-
- ハフマン符号：データ圧縮に使用されるアルゴリズムで、最適なハフマンツリーを構築する必要があります。
-
- ダイクストラのアルゴリズム：グラフの単一始点最短経路問題を解くために使用されます。
-
- 分数ナップサック問題：0-1 ナップサック問題と似ていますが、アイテムを分割することができます。総価値を最大化するためにどのようにアイテムを選択し、分割するかを決定する必要があります。
-
- クラスカルのアルゴリズムとプリムのアルゴリズム：グラフの最小全域木問題を解くために使用されます。