Hebzuchtig algoritme

In deze tutorial leer je wat een Greedy Algorithm is. Ook vindt u een voorbeeld van een hebzuchtige benadering.

Een hebberig algoritme is een benadering om een ​​probleem op te lossen door de beste optie te selecteren die op dit moment beschikbaar is, zonder je zorgen te maken over het toekomstige resultaat dat het zou opleveren. Met andere woorden, de plaatselijk beste keuzes zijn gericht op het produceren van wereldwijd de beste resultaten.

Dit algoritme is misschien niet de beste optie voor alle problemen. Het kan in sommige gevallen verkeerde resultaten opleveren.

Dit algoritme gaat nooit terug om de genomen beslissing terug te draaien. Dit algoritme werkt van bovenaf.

Het belangrijkste voordeel van dit algoritme is:

  1. Het algoritme is gemakkelijker te beschrijven .
  2. Dit algoritme kan beter presteren dan andere algoritmen (maar niet in alle gevallen).

Haalbare oplossing

Een haalbare oplossing is degene die de optimale oplossing voor het probleem biedt.

Hebzuchtig algoritme

  1. Om te beginnen is de oplossingsset (met antwoorden) leeg.
  2. Bij elke stap wordt een item toegevoegd aan de oplossingsset.
  3. Als de oplossingsset haalbaar is, wordt het huidige item behouden.
  4. Anders wordt het item afgekeurd en nooit meer in overweging genomen.

Voorbeeld - hebzuchtige aanpak

 Probleem: u moet een bedrag wijzigen met een zo klein mogelijk aantal munten. Bedrag: $ 28 Beschikbare munten: $ 5 muntstuk $ 2 muntstuk $ 1 munt

Oplossing:

  1. Maak een lege oplossingsset = ().
  2. munten = (5, 2, 1)
  3. som = 0
  4. Doe bij som ≠ 28 het volgende.
  5. Selecteer een munt C uit munten met de som + C <28.
  6. Als C + som> 28, retourneer geen oplossing.
  7. Anders, som = som + C.
  8. Voeg C toe aan de oplossingsset.

Tot de eerste 5 iteraties bevat de oplossingsset 5 munten van $ 5. Daarna krijgen we 1 munt van $ 2 en tot slot 1 munt van $ 1.

Hebzuchtige algoritmetoepassingen

  • Selectie sorteren
  • Knapzak probleem
  • Minimale overspanningsboom
  • Kortste padprobleem met één bron
  • Probleem met taakplanning
  • Prim's Minimal Spanning Tree-algoritme
  • Kruskal's Minimal Spanning Tree-algoritme
  • Dijkstra's Minimal Spanning Tree-algoritme
  • Huffman-codering
  • Ford-Fulkerson-algoritme

Interessante artikelen...