ダイナミックプログラミングまたは貪欲方法を使用した問題の解決策？

Question

どのようなプロパティに問題があるので、どのメソッドを動的プログラミングや欲張りメソッドを使用するか決定できますか？

Answer 1

動的プログラミングの問題は、最適な部分構造を示します。これは、問題に対する解を、厳密に小さいサブ問題に対する解の関数として表すことができることを意味する。

このような問題の1つの例は、matrix chain multiplicationです。

欲張りアルゴリズムは、ローカル最適な選択が完全に最適な解決につながる場合にのみ使用できます。これは直ちに見るのが難しいかもしれませんが、一般的に実装するのは簡単です（複数の小さな問題のすべての解決策ではなく、貪欲な選択肢）。

有名なグリーディアルゴリズムの1つは、最小スパニングツリーを見つけるためのKruskal's algorithmです。

Answer 2

それを知ることは本当に厳しいルールです。誰かがすでに言ったように、赤いライトを点灯させるべきことがいくつかありますが、最後には経験だけがあなたに伝えることができます。

Answer 3

Cormen、Leiserson、Rivest and Stein's Algorithmsの第2版には、欲張り方法が最適解を生み出す時期について説明する「欲張り方法の理論基盤」（16.4節）があります。実際の興味の多くのケースをカバーしていますが、最適な結果をもたらすすべての欲張りアルゴリズムがこの理論の観点から理解できるわけではありません。

また、動的プログラミングから欲張りアルゴリズムへのリンクhereも出てきました。特定の欲張りアルゴリズムについて語っているのは、動的プログラミングの改良点です。クイックスキャンから、あなたにとって興味深いかもしれません。

Answer 4

各段階で利用可能なローカル情報を決定する際には、欲張り方法を適用します。各段階で決定された一連の決定に従って、最適な解決策を見つけることができます。 しかし、ダイナミックなアプローチでは、一段階で意思決定を行うことが確実でない可能性があります。そのため、可能性の高い要素の1つを解決する可能性のある決定を行います。