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

この投稿では、欲張りアルゴリズムと動的計画法の違いを理解します。

欲張りアルゴリズム

これは、段階的にソリューションを部分的に構築するアルゴリズムパラダイムです。次のステップは、最も明白で即時の利益が得られるように選択されます。

• ローカル最適値の選択を伴う問題は、グローバル最適値/問題の解決策を選択するのに役立ちます。そのようなものは欲張りアルゴリズムに関連する問題を食べました。
• 欲張りアルゴリズムが最適なソリューションにつながるかどうかは定かではありません。
• 問題のすべての段階で最適な選択が行われます。つまり、局所的な最適解です。
• 以前のソリューション/値に戻ったり変更したりする必要がないため、メモリ使用量の点で効率的です。
• 一般に、動的計画法に比べて高速です。
• 例：O（ELogV + VLogV）時間を要するダイクストラの最短経路アルゴリズム。
• 欲張りアルゴリズムの解はフォワード法で計算され、以前の値/解にアクセスしたり、それらを変更したりすることはありません。

動的計画法

これは、サブ問題の結果を保存して、将来必要になったときに再計算する必要がないようにするのに役立つ最適化手法です。それらは、事前に計算されたセットから抽出することができます。時間計算量を指数関数から多項式の複雑さに減らします。

• 例：再帰的ソリューションは、コンピューティングによって動的計画問題に変えることができます。
• この場合、すべてのステップで行われる決定は、手元にある現在の問題と、以前に解決された合計問題の解決策を考慮して行われます。これは、最適な値/ソリューションを計算するために使用されます。
• 動的計画問題の解決策が最適なものになることが保証されています。
• ここで選択される最適なソリューションは、グローバルに最適なソリューションです。以前に計算された状態値を格納するために使用されたであろう特定の式を使用します。
• 暗記には動的計画法の表が必要です。これにより、メモリが複雑になります。
• 比較的遅いです。
• 例：O（VE）時間を要するベルマンフォードアルゴリズム。
• 動的計画法は、最適な解決策を持つ小さな問題から開発することにより、ボトムアップまたはトップダウンのアプローチを使用して解決策を決定します。