欲張り法と動的計画法の主な違いは、 欲張り法によって行われる決定（選択）は、これまでに行われた決定（選択）に依存し、将来の選択またはサブ問題のすべての解決策に依存しません。一方、動的計画法は、問題を解決するために前の段階で行われたすべての決定に基づいて決定を行います。

アルゴリズムは、問題を解決するための体系的な一連の手順です。欲張り法と動的計画法は2つのアルゴリズムです。どちらも最適化問題を解くために使用されます。

欲張り法、動的計画法

欲張り法とは

欲張り法では、複数の現在価値から最適なオプションを見つけます。この方法では、最初の段階を考慮し、将来の出力を考慮せずに出力を決定します。言い換えると、欲張りアルゴリズムは、その特定の瞬間に最適なオプションを検討することによって問題を解決します。

欲張りアルゴリズムは、問題に欲張り選択プロパティと最適部分構造の2つのプロパティが含まれている場合に機能します。ローカルに最適なソリューションを作成することにより、グローバルに最適なソリューションを見つけることができます。言い換えれば、貪欲な選択を作成することは、最適な解決策を見つけるのに役立ちます。したがって、このプロパティは欲張り選択プロパティと呼ばれます。さらに、最適解には最適サブ解が含まれます。したがって、このプロパティは最適部分構造と呼ばれます。

動的計画法とは

動的計画法では、主要な問題を小さなサブ問題に分割します。このメソッドは、サブ問題の結果を保存し、それらを同様のサブ問題に適用します。ここでは、サブ問題の回答を保存することを暗記と呼びます。サブ問題の答えをチェックし、最終的に最適または最良の解決策を見つけるための結論に達します。動的計画法は以前の回答をチェックし、同じ回答を複数回計算することを回避するため、より効率的です。

動的計画法では、主な問題の最適解は、その副問題の最適解の範囲内にあります。さらに、同じサブ問題に何度も直面する状況がある場合、それは重複サブ問題と呼ばれます。

欲張り法と動的計画法の違い

意味

欲張り法は、グローバルな最適化を見つけることを目的として、各店舗でローカルに最適な選択を行うという問題解決ヒューリスティックに従うアルゴリズムです。一方、動的計画法は、重複するサブ問題と最適な部分構造特性を持つ問題のクラスを効率的に解決するのに役立つアルゴリズムです。これらの定義は、欲張り法と動的計画法の主な違いを説明しています。

効率

さらに、欲張り法と動的計画法の主な違いは、その効率です。貪欲法は効率が低く、動的計画法はより効率的です。

プロセス

意思決定

意思決定の方法は、欲張り法と動的計画法のさらに別の違いです。欲張り法は最初の段階を考慮して決定を下し、動的計画法はすべての段階で決定を下します。

結論

欲張り法によって行われる決定（選択）は、これまでに行われた決定（選択）に依存し、将来の選択またはサブ問題のすべての解決策に依存しません。ただし、動的計画法は、問題を解決するために前の段階で行われたすべての決定に基づいて決定を行います。これが欲張り法と動的計画法の主な違いです。

リファレンス：

1.「動的計画法の概要–Javatpoint」。 Www.javatpoint.com、ここから入手可能2。動的計画法|設計とアプリケーションの手順|、Education 4u、2018年4月2日、こちらから入手可能3。 「欲張りアルゴリズムの紹介–Javatpoint」 Www.javatpoint.com、こちらから入手可能4。 「欲張りアルゴリズム」。ウィキペディア、ウィキメディア財団、2018年10月9日、こちらから入手できます。

画像提供：

1. Swfung8による「Greedy-search-path-example」– Commons Wikimedia2を介した自作（CC BY-SA 3.0）。 「フィボナッチ動的計画法」en：User：Dcoatzee著、User：Stanneredによる追跡– en：Image：Fibonacci動的計画法.png（ドミニプブリック）コモンズウィキメディア経由