algorithm - 動的計画法または貪欲な方法を使用した問題の解決策は?

Question

動的計画法または貪欲な方法のどちらを使用するかを決定できるように、問題にはどのようなプロパティが必要ですか?

Answer 1

動的計画問題は最適な部分構造を示します。これは、問題の解決策が、厳密に小さいサブ問題の解決策の関数として表現できることを意味します。

このような問題の一例は、行列の連鎖乗積です。

欲張りアルゴリズムは、局所的に最適な選択が完全に最適なソリューションにつながる場合にのみ使用できます。これはすぐにはわかりにくい場合がありますが、複数（すべての小さなサブ問題の解決策）ではなく、考慮すべきことが1つ（貪欲な選択）しかないため、一般に実装が簡単です。

有名な欲張りアルゴリズムの1つは、最小全域木を見つけるためのクラスカルのアルゴリズムです。

Answer 2

Cormen、Leiserson、Rivest、および Stein の Algorithms 本の第 2 版には、「欲張りな方法の理論的基礎」というタイトルのセクション (16.4) があり、欲張りな方法がいつ最適解をもたらすかについて説明しています。実際に興味深い多くのケースをカバーしていますが、最適な結果をもたらす貪欲なアルゴリズムのすべてがこの理論の観点から理解できるわけではありません。

また、「動的プログラミングから貪欲なアルゴリズムへ」というタイトルの論文に出くわしました。ここにリンクされている特定の貪欲なアルゴリズムは、動的プログラミングの改良と見なすことができます。簡単なスキャンから、それはあなたにとって興味があるかもしれません.

Answer 3

それを知るには本当に厳しいルールがあります。すでに誰かが言ったように、赤信号をオンにする必要があることがいくつかありますが、最終的には、経験だけがあなたに伝えることができます。

Answer 4

各段階で利用可能なローカル情報に基づいて決定を下すことができる場合、貪欲な方法を適用します。各段階での一連の決定に従って、最適な解決策を見つけることができると確信しています。ただし、動的なアプローチでは、ある段階で決定を下すことについて確信が持てない場合があるため、可能性のある決定のセットを実行します。可能性のある要素の 1 つが解決につながる可能性があります。