algorithm - 欲張り vs ダイナミック

Question

アルゴリズムに関する一般的な質問があります。問題があり、アルゴリズムを書きたい場合、問題にどのようにアプローチしますか、貪欲なアルゴリズムまたは動的プログラミングを使用するアルゴリズムをどのように決定しますか? 前もって感謝します

Answer 1

一般に、私は新しい問題を、よく知られた解決策を持つよく知られた問題に変換しようとします。次に、適切なアルゴリズムを選択するのは簡単です。私の経験では、これは実際のほとんどのケースをカバーしています。

ステップ 1 が失敗した場合、貪欲なアプローチを試み、それが機能しないことを証明しようとします。証明の部分はややこしいかもしれませんが、基本的には、中間ステップで局所的に最良の選択をしても、全体として最良の結果が得られないことを示す必要があります。そこから私は分岐し、通常、動的は私が試す最初の選択肢の 1 つです。

他のすべてが失敗した場合、目前の問題に十分に近い適切な近似アルゴリズムを調べ始めます。多くの問題は、時間とリソースのほんの一部で近似を使用して「十分に」解決できるため、明確な勝者になります。

Answer 2

貪欲なアルゴリズムが機能する場合は、そうでない場合は、動的計画法が機能する場合はそれを選択し、そうでない場合は漸近的な動作が悪いものを選択します。

あなたの質問に対する答えを得ることをどうして真剣に期待できますか?

すべての動的計画法のタスクには、(適切に選択された) サブ問題の最適解が、問題全体の最適解の一部でもあるという特徴があります。問題のこの機能を発見するか、発見しないかのどちらかです...

更新：「よく知られている同様の問題にマップする」という素晴らしい答えをお伝えしたいと思いますが、それは私がしていることではありません。私はいくつかの DP 問題を解決しました。それ以来、ブルート フォース アルゴリズムで O(2^n) を生成するものを見つけた場合、最適なソリューションを構築できるサブ問題の検索を自動的に開始します。