DAA-欲張り法

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

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

多くの問題では、妥当な時間で近似（ほぼ最適）な解が得られますが、最適な解は生成されません。

欲張りアルゴリズムのコンポーネント

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

• A candidate set −このセットからソリューションが作成されます。

• A selection function −ソリューションに追加する最適な候補を選択するために使用されます。

• A feasibility function −候補を使用してソリューションに貢献できるかどうかを判断するために使用されます。

• An objective function −ソリューションまたは部分ソリューションに値を割り当てるために使用されます。

• A solution function −完全な解決策に到達したかどうかを示すために使用されます。

適用分野

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

• ダイクストラのアルゴリズムを使用して、2つの頂点間の最短経路を見つけます。

• プリム/クラスカルのアルゴリズムなどを使用して、グラフ内の最小全域木を見つける。

欲張りアプローチが失敗する場所

多くの問題で、欲張りアルゴリズムは最適な解決策を見つけることができず、さらに最悪の解決策を生み出す可能性があります。巡回セールスマンやナップザックのような問題は、このアプローチでは解決できません。