貪欲なアプローチと動的計画法
1. 概要
問題に直面したとき、それを解決するための複数のアプローチを検討することができます。 最もよく聞かれる質問の1つは、greedyアプローチと動的計画法の違いです。
このチュートリアルでは、2つの概念を説明し、それらの比較を提供します。
2. 欲張りアプローチ
2.1. 理論的アイデア
貪欲なアプローチを使用して問題を解決することは、問題を段階的に解決することを意味します。 各ステップで、アルゴリズムは、ヒューリスティックに基づいて、最も明白で有益な利益を達成する選択を行います。 アルゴリズムは、常に達成できるとは限りませんが、最適なソリューションを達成することを望んでいます。
欲張りアプローチは、局所的な最適性が最適なグローバルソリューションにつながる問題に適しています。
2.2. 例
欲張りアプローチを使用して解決できる問題の例を見てみましょう。
一連のアクティビティが与えられているとしましょう。 各アクティビティには、開始時刻と終了時刻があります。 交差しない、つまり一人で実行できるアクティビティの最大数を見つけるように求められます。
貪欲なアプローチは、常に最も早い終了時刻のアクティビティを選択することです。ヒューリスティックの最適性を証明しましょう。
後で終了するアクティビティを選択するとします。 この場合、次のステップのオプションを制限しました。 つまり、終了時間が最も早いアクティビティでは、次のステップで選択できるアクティビティが増えます。
したがって、最も早い終了時刻を選択することで、この問題に対する完全に最適なソリューションが得られるはずです。
説明したアルゴリズムの実装を見てみましょう。
まず、以前の終了時間に基づいてアクティビティのリストを並べ替えます。 次に、アクティビティを繰り返して、最初に実行できるアクティビティを選択します。 アクティビティの開始時刻が最後に選択したアクティビティの終了時刻よりも遅い場合は、このアクティビティを取得して、現在の終了時刻を更新します。
上記のアルゴリズムの合計時間計算量はです。ここで、はアクティビティの合計数です。 この複雑さの理由は、で実装できるソート操作ですが、反復の複雑さは。
DijkstraおよびPrimのアルゴリズムも、欲張り問題のよく知られた例です。
2.3. 反例
欲張りアプローチは理解可能で実装が簡単に見えるかもしれませんが、欲張りアプローチを使用して解決できない問題もあります。
たとえば、0/1ナップザックの問題は貪欲なアプローチでは解決できません。 問題を解決するときに欲張りアプローチを使用するには、まず、ローカルの最適性がグローバルな最適性につながることを証明する必要があります。
3. 動的計画法
3.1. 理論的アイデア
ほとんどすべての問題は、再帰バックトラッキングアプローチを使用して解決できます。 ただし、このアプローチには通常、指数関数の時間計算量があります。
指数関数的な時間計算量の理由は、同じ状態を複数回訪問することから生じる可能性があります。
動的計画法は、すでに計算された状態を保存するという考えから生まれました。 状態の答えを計算するときは、最初に、以前に同じ状態を計算したことがあるかどうかを確認します。 この状態をすでに計算している場合は、その答えを返すことができます。 それ以外の場合は、この状態の答えを計算して保存する必要があります。
このアプローチは、トップダウン動的計画法と呼ばれます。 ただし、主に同じ考え方を持つボトムアップアプローチと呼ばれる別のアプローチがあります。
違いは、ボトムアップアプローチは小さなサブ問題から始まり、大きなサブ問題の答えを構築しようとすることです。 このプロセスは、問題全体の解決策に到達するまで続きます。
動的計画法を使用する主な利点は、バックトラッキングバージョンの指数関数的な時間計算量ではなく、多項式時間計算量に移行することです。 また、動的計画法は、正しく実装されていれば、最適なソリューションが得られることを保証します。
動的計画法の最適化の背後にある理由は、それがすべての可能な選択肢を探索するバックトラッキングアプローチに対する最適化であるということです。
3.2. 例
動的計画法に関しては、0/1ナップザックと最長増加部分列の問題から始めるのが一般的です。
とにかく、前述の問題に対する動的計画法の解決策を示しましょう。
まず、以前の開始時間に基づいてアクティビティのリストを並べ替えます。 i番目の状態には、範囲内で実行できるアクティビティの最大数が格納されます。
基本的なサブ問題は、リストの最後に到達すると、アクティビティを実行できないことです。 次に、アクティビティを降順で繰り返します。 アクティビティごとに、現在のアクティビティを終了して、次のアクティビティに移動できます。 この場合、の答えを取ります。
それ以外の場合は、現在のアクティビティを選択できます。 これは、移動する次のアクティビティを見つける必要があることを意味します。これは、getNext関数が計算しているものです。 次のアクティビティは、現在のアクティビティが終了した直後に開始するアクティビティです。
その後、現在のアクティビティを選択したため、現在の状態に対する答えは、次の状態を1つ増やしたものと同じになります。 最後に、i th 状態に対する答えは、これら2つの選択肢の間の最大値です。 最終的な回答はに保存されます。
getNext 関数の複雑さのため、このアルゴリズムには時間計算量があります。 ただし、配列は並べ替えられているため、バイナリ検索を実行して次のアクティビティを取得できます。 したがって、合計時間計算量はに減少します。
最適化の理由は、各ステップですべての可能な選択肢を検討するためです。 その後、サブ問題全体で最大の利益をもたらすものを選択します。 また、各ステップは、同じアプローチを使用してすでに計算した次の状態に依存します。
3.3. 反例
再帰的アプローチが同じ状態に対して多くの呼び出しを行わない場合、動的計画法を使用することは良い考えではないかもしれません。 たとえば、移動セールスマンの問題は、動的計画法を使用して解決することはできません。
4. 比較
表を見ると、欲張りアプローチと動的計画法の主な違いと類似点がわかります。
一般に、貪欲なアプローチを使用して問題を解決できる場合は、通常、それが最善の選択です。
ただし、一部の問題は、非常に複雑な欲張りアプローチを必要とする場合や、このアプローチを使用して解決できない場合があります。 この場合、動的計画法のアプローチを実装するために、再帰的ソリューションを最適化しようとします。
5. 結論
このチュートリアルでは、貪欲なアプローチと動的計画法の背後にある主なアイデアを、それぞれのアプローチの例とともに説明しました。
また、両方のアプローチを使用して解決できる問題と解決できない問題の例をさらに示しました。
最後に、2つのアプローチの基本的な比較を示して要約しました。
