Data-structures-algorithms-greedy-algorithms
データ構造-貪欲なアルゴリズム
アルゴリズムは、特定の問題に対して最適なソリューションを実現するように設計されています。 貪欲なアルゴリズムアプローチでは、特定のソリューションドメインから決定が行われます。 貪欲であるため、最適なソリューションを提供すると思われる最も近いソリューションが選択されます。
貪欲なアルゴリズムは、ローカライズされた最適なソリューションを見つけようとしますが、最終的にはグローバルに最適化されたソリューションにつながる可能性があります。 ただし、一般的に貪欲なアルゴリズムは、グローバルに最適化されたソリューションを提供しません。
コインを数える
この問題は、可能な限り最小のコインを選択することにより、望ましい値にカウントすることであり、貪欲なアプローチは、アルゴリズムに可能な限り最大のコインを選択させる。 私たちが£1、2、5、および10のコインを提供され、£18を数えるように求められた場合、貪欲な手順は次のようになります-
- 1 -£10コインを1つ選択します。残りのカウントは8です
- 2 -その後、1つの£5コインを選択します。残りのカウントは3です
- 3 -次に1つの£2コインを選択します。残りのカウントは1です
- 4 -そして最後に、1コインを1枚選択すると問題が解決します
しかし、それはうまく機能しているように見えますが、このカウントのために私たちはたった4枚のコインを選ぶ必要があります。 ただし、問題をわずかに変更すると、同じアプローチでは同じ最適な結果が得られない場合があります。
値が1、7、10のコインがある通貨システムでは、値18のコインを数えることは絶対に最適ですが、15のようなカウントでは必要以上のコインを使用する可能性があります。 たとえば、貪欲なアプローチでは10＆plus;を使用します。 1＆plus; 1＆plus; 1＆plus; 1＆plus; 1、合計6コイン。 同じ問題は、3枚のコイン（7＆plus; 7＆plus; 1）を使用するだけで解決できますが、
したがって、貪欲なアプローチは即座に最適化されたソリューションを選択し、グローバルな最適化が主要な関心事である場合に失敗する可能性があると結論付けることができます。
例
ほとんどのネットワークアルゴリズムは、貪欲なアプローチを使用します。 ここにそれらのいくつかのリストがあります-
- 巡回セールスマン問題
- プリムの最小スパニングツリーアルゴリズム
- クラスカルの最小スパニングツリーアルゴリズム
- ダイクストラの最小スパニングツリーアルゴリズム
- グラフ-地図の色付け
- グラフ-頂点カバー
- ナップザックの問題
- ジョブスケジューリングの問題
貪欲なアプローチを使用して最適なソリューションを見つける同様の問題がたくさんあります。
