Design-and-analysis-of-algorithms-greedy-method

DAA-貪欲な方法

すべてのアルゴリズム的アプローチの中で、最も単純で簡単なアプローチは貪欲法です。 このアプローチでは、将来の現在の決定の影響を心配することなく、現在の利用可能な情報に基づいて決定が行われます。

貪欲なアルゴリズムは、解決策を部分的に構築し、次の部分をそのような方法で選択することで、即座に利益をもたらします。 このアプローチは、以前の選択を再考することはありません。 このアプローチは、主に最適化の問題を解決するために使用されます。 貪欲な方法は実装が簡単で、ほとんどの場合非常に効率的です。 したがって、Greedyアルゴリズムはヒューリスティックに基づいたアルゴリズムパラダイムであり、グローバルな最適解を見つけることを期待して、各ステップでローカルの最適な選択に従うと言えます。

多くの問題では、妥当な時間で近似（最適に近い）解決策を提供しますが、最適な解決策を生成しません。

貪欲なアルゴリズムのコンポーネント

貪欲なアルゴリズムには、次の5つのコンポーネントがあります-

• 候補セット-このセットからソリューションが作成されます。
• 選択機能-ソリューションに追加する最適な候補を選択するために使用します。
• 実現可能性関数-候補を使用してソリューションに貢献できるかどうかを判断するために使用されます。
• 目的関数-解または部分解に値を割り当てるために使用されます。
• ソリューション関数-完全なソリューションに到達したかどうかを示すために使用されます。

適用分野

貪欲なアプローチは、次のような多くの問題を解決するために使用されます

• ダイクストラのアルゴリズムを使用して、2つの頂点間の最短経路を見つけます。
• Primの/Kruskalのアルゴリズムなどを使用して、グラフで最小スパニングツリーを見つける

貪欲なアプローチが失敗する場所

多くの問題で、Greedyアルゴリズムは最適なソリューションを見つけられず、さらに最悪のソリューションを生成する可能性があります。 巡回セールスマンやナップザックなどの問題は、このアプローチでは解決できません。