43

私が使用している本で、アルゴリズムの設計と分析の紹介では、動的計画法は最適化の原則に焦点を当てていると言われています。

一方、貪欲な手法は、完全な問題の解決策に到達するまで、部分的に構築された解決策を拡張することに重点を置いています。次に、「そのステップで利用可能なすべての実行可能な選択肢の中で最良のローカルな選択肢」でなければならないと言われています。

どちらも局所最適性を伴うため、一方は他方のサブセットではありませんか?

4

7 に答える 7

53

動的計画法は、次の特性を示す問題に適用できます。

  • 部分問題の重複、および
  • 最適な下部構造。

最適な部分構造とは、貪欲に部分問題を解決し、解決策を組み合わせてより大きな問題を解決できることを意味します。 動的計画法と貪欲なアルゴリズムの違いは、動的計画法では重複する部分問題があり、それらの部分問題は memoization を使用して解決されることです。「メモ化」とは、サブ問題の解決策を使用して、他のサブ問題をより迅速に解決する手法です。

この回答は注目を集めているので、いくつか例を挙げます。

「ドル、ニッケル、ペニーで両替する」という問題を考えてみましょう。これは貪欲な問題です。ドルの数を解くことができるため、最適な部分構造が示されます。次に、ニッケルの数を解きます。次に、ペニーの数。その後、これらのサブ問題に対するソリューションを効率的に組み合わせることができます。各サブ問題を解決しても他のサブ問題にはあまり役立たないため (おそらく少し)、重複するサブ問題は実際には見られません。

「フィボナッチ数」という問題を考えてみましょう。F(9) と F(8) から F(10) を効率的に (加算により) 解くことができるため、最適な部分構造を示します。これらのサブ問題は、両方とも F(7) を共有しているため、重複しています。F(8) を解くときに F(7) の結果をメモしておくと、F(9) を早く解くことができます。

「決定の再考」に関係する動的計画法に関するコメントへの回答: これは、上記の最大部分配列問題やフィボナッチ問題のような線形動的計画法アルゴリズムには明らかに当てはまりません。

基本的に、ノードが部分問題を表し (問題全体が次数がゼロのノードで表される)、有向辺が部分問題間の依存関係を表す有向非巡回グラフとして、最適な部分構造を持つ問題を想像してください。次に、貪欲な問題はツリーです（ルートを除くすべてのノードには次数の単位があります）。動的計画法の問題には、次数が 1 より大きいノードがいくつかあります。これは、重複する部分問題を示しています。

于 2012-12-04T23:18:59.200 に答える
12

違いは、動的計画法では小さな状態の答えを覚えておく必要があるのに対し、貪欲なアルゴリズムは必要なすべての情報が現在の状態にあるという意味でローカルです。もちろん交差点もあります。

于 2012-12-04T23:13:21.740 に答える
9

重要な違いは、貪欲なアルゴリズムが「静的に」ソリューションを構成することです。これは、ソリューション内の各ローカル選択を、他のローカル選択について何も知る必要なく最終決定できるという意味です。ただし、動的アルゴリズムは、サブ問題に対する可能なソリューションのセットを作成し、すべてのサブ問題が考慮されたときに、グローバルな問題に対する単一のソリューションのみを生成します。貪欲なアルゴリズムに関するウィキペディアのページでは、次のように説明されています。

貪欲なアルゴリズムによる選択は、これまでの選択に依存する可能性がありますが、将来の選択や部分問題のすべての解には依存しません。貪欲な選択を次々と繰り返し行い、与えられた各問題をより小さな問題に減らします。言い換えれば、貪欲なアルゴリズムはその選択を決して再考しません。これは、網羅的であり、解を見つけることが保証されている動的計画法との主な違いです。各段階の後、動的計画法は、前の段階で行われたすべての決定に基づいて決定を行い、前の段階のソリューションへのアルゴリズム パスを再検討する場合があります。

于 2012-12-05T00:14:43.790 に答える
6

DP アルゴリズムは、(いくつかの問題について) という事実を使用します - サイズの問題に対するn最適な解は、サイズの問題に対する最適な解で構成され、n'<nこれを使用して、最小の問題から必要な問題まで、ボトムアップで解を構築します。サイズ。

これは、同じ再帰の原則に非常によく適合します (問題をより小さな部分問題に縮小し、再帰的に呼び出す)。実際、DP ソリューションは再帰的な式として表されることがよくあります。

貪欲なアルゴリズムは、ローカルポイントを見て、このポイントでデータを選択します。一部の問題 (負の重みのない最短経路など) では、この局所的な選択が最適な解につながります。

2 つのアプローチの違いの良い例は、最短経路問題です。

  • Dijsktra のアルゴリズムは貪欲なアプローチです (各ステップで、そのノードへのパスが現在最小化されているノードを選択します。この選択は、アルゴリズムのローカル状態に基づいて貪欲に行われます)。
  • Bellman-Ford アルゴリズムは DP ソリューションです (すべてのエッジを「リラックス」して問題を効果的に軽減します)。
于 2012-12-04T23:10:54.283 に答える