54

使用法における動的プログラミングと貪欲なアプローチの主な違いは何ですか?

私が理解している限りでは、貪欲なアプローチによって最適な解決策が得られる場合があります。それ以外の場合は、動的計画法のアプローチが最適なソリューションを提供します。

1 つのアプローチ (または別のアプローチ) を使用して最適なソリューションを得るために満たす必要がある特定の条件はありますか?

4

6 に答える 6

83

ウィキペディアの記事に基づいています。

貪欲なアプローチ

貪欲なアルゴリズムは、グローバルな最適を見つけることを期待して、各段階で局所的に最適な選択を行う問題解決ヒューリスティックに従うアルゴリズムです。多くの問題では、貪欲な戦略は一般に最適解を生成しませんが、それでも貪欲なヒューリスティックは、適切な時間内にグローバル最適解に近似するローカル最適解を生成する可能性があります。

現時点で最善と思われる選択を行い、後で発生する副次的な問題を解決できます。貪欲なアルゴリズムによる選択は、これまでの選択に依存する場合がありますが、将来の選択や部分問題のすべての解には依存しません。貪欲な選択を次々と繰り返し行い、与えられた各問題をより小さな問題に減らします。

動的計画法

動的計画法の背後にある考え方は非常に単純です。一般に、特定の問題を解決するには、問題のさまざまな部分 (副問題) を解決し、副問題の解決策を組み合わせて全体的な解決策に到達する必要があります。多くの場合、より単純な方法を使用すると、副問題の多くが生成され、何度も解決されます。動的計画法のアプローチでは、各部分問題を1 回だけ解こうとするため、計算回数が削減されます。特定の部分問題の解が計算されると、それは保存または「メモ化」されます。次に同じ解が必要になったときに、単に見上げられます。このアプローチは、繰り返されるサブ問題の数が入力のサイズの関数として指数関数的に増加する場合に特に役立ちます。

違い

貪欲な選択プロパティ

現時点で最善と思われる選択を行い、後で発生する副次的な問題を解決できます。貪欲なアルゴリズムによる選択は、これまでの選択に依存する場合がありますが、将来の選択や部分問題のすべての解には依存しません。貪欲な選択を次々と繰り返し行い、与えられた各問題をより小さな問題に減らします。言い換えれば、貪欲なアルゴリズムはその選択を決して再考しません。

これは、網羅的であり、解を見つけることが保証されている動的計画法との主な違いです。各ステージの後、動的計画法は、前のステージで行われたすべての決定に基づいて決定を行い、前のステージのソリューションへのアルゴリズム パスを再検討する場合があります。

たとえば、特定の都市のラッシュアワー中に、ポイント A からポイント B にできるだけ速く移動する必要があるとします。ダイナミック プログラミング アルゴリズムは、交通レポート全体を調べて、あなたがたどる可能性のある道路のすべての可能な組み合わせを調べてから、どの道が最速かを教えてくれます。もちろん、アルゴリズムが終了するまでしばらく待たなければならない場合があります。その後、運転を開始できます。あなたがたどる道は最速のものです（外部環境で何も変わっていないと仮定して）。

一方、貪欲なアルゴリズムはすぐに運転を開始し、すべての交差点で最も速く見える道路を選択します。ご想像のとおり、この戦略は最速の到着時間にはつながらない可能性があります。「簡単な」道路をいくつか通過した後、絶望的に交通渋滞に巻き込まれる可能性があるからです。

その他の詳細...

数学的最適化では、貪欲なアルゴリズムがマトロイドの特性を持つ組み合わせ問題を解決します。

動的計画法は、重複部分問題と最適部分構造の特性を示す問題に適用できます。

于 2013-09-12T13:29:14.300 に答える
1

貪欲な方法と動的計画法の違いを以下に示します。

  1. 貪欲な方法はその選択を再考することはありませんが、動的プログラミングは以前の状態を考慮する可能性があります。

  2. 貪欲アルゴリズムはあまり効率的ではありませんが、動的計画法はより効率的です。

  3. 貪欲なアルゴリズムには部分問題のローカルな選択がありますが、動的プログラミングはすべての部分問題を解決してから、最適な解決策につながるものを選択します。

  4. 貪欲なアルゴリズムは一度に決定を下しますが、動的プログラミングはすべての段階で決定を下します。

于 2018-10-27T01:28:11.117 に答える
0

簡単に言えば、Dynamic Programming（ネットワーク上でメッセージを送信するのに問題がある場合）では、最初に最短時間の経路を調べてから、旅を始めることができます。

一方、次のステップを考えずにその場でGreedy algorithm取り、optimal decision次のステップで再び決定を変更するなど...

Notes: Dynamic programming貪欲アルゴリズムは常に信頼できるとは限りませんが、信頼できます。

于 2016-07-19T06:05:13.383 に答える
0

Biswajit Roy の参照: Dynamic Programming はまず計画を立て、次に Go を実行します。貪欲なアルゴリズムは貪欲な選択を使用し、最初にGo、次に継続的に計画します。

于 2018-11-06T16:53:44.377 に答える