データ構造-欲張りアルゴリズム

アルゴリズムは、特定の問題に対して最適なソリューションを実現するように設計されています。欲張りアルゴリズムのアプローチでは、決定は特定のソリューションドメインから行われます。貪欲であるため、最適なソリューションを提供すると思われる最も近いソリューションが選択されます。

欲張りアルゴリズムは、ローカライズされた最適なソリューションを見つけようとします。これにより、最終的にはグローバルに最適化されたソリューションにつながる可能性があります。ただし、一般的に欲張りアルゴリズムは、グローバルに最適化されたソリューションを提供しません。

コインを数える

この問題は、可能な限り最小のコインを選択することによって目的の値にカウントすることであり、貪欲なアプローチにより、アルゴリズムは可能な限り最大のコインを選択するように強制されます。1、2、5、10ポンドのコインが提供され、18ポンドを数えるように求められた場合、貪欲な手順は次のようになります。

1 −£10コインを1つ選択すると、残りのカウントは8になります
2 −次に、5ポンド硬貨を1枚選択すると、残りの数は3になります。
3 −次に、2ポンド硬貨を1枚選択すると、残りの数は1になります。
4 −そして最後に、1枚の1ポンド硬貨を選択することで問題が解決します

うまく機能しているようですが、このカウントでは4枚のコインを選ぶだけで済みます。しかし、問題を少し変えると、同じアプローチでは同じ最適な結果が得られない可能性があります。

1、7、10の値のコインがある通貨システムの場合、値18のコインを数えるのが絶対に最適ですが、15のような数の場合、必要以上のコインを使用する可能性があります。たとえば、欲張りアプローチでは、10 + 1 + 1 + 1 + 1 + 1、合計6コインを使用します。同じ問題は3枚のコイン（7 + 7 + 1）だけを使用することで解決できましたが

したがって、貪欲なアプローチは即座に最適化されたソリューションを選択し、グローバルな最適化が主要な懸念事項である場合は失敗する可能性があると結論付けることができます。

例

ほとんどのネットワークアルゴリズムは欲張りアプローチを使用します。ここにそれらのいくつかのリストがあります-

巡回セールスマン問題
プリムの最小スパニングツリーアルゴリズム
クラスカルの最小スパニングツリーアルゴリズム
ダイクストラの最小スパニングツリーアルゴリズム
グラフ-マップのカラーリング
グラフ-頂点被覆
ナップサック問題
ジョブスケジューリング問題

貪欲なアプローチを使用して最適な解決策を見つける同様の問題がたくさんあります。