Wat is een greedy algoritme en in welke gevallen wordt het toegepast?

De greedy-algoritme is een aanpak voor het oplossen van optimalisatieproblemen waarbij bij elke stap de beste lokale oplossing (de meest voordelige optie vanuit het huidige moment) wordt gekozen in de hoop dat deze reeks van optimale lokale oplossingen leidt tot een globale optimale oplossing. Het houdt geen rekening met de mogelijke gevolgen van de huidige keuze voor de toekomstige stappen.

Kenmerken:

• Eenvoud: Over het algemeen gemakkelijker te implementeren dan dynamische programmering of andere optimalisatiemethoden.
• Snelheid: Heeft vaak een lagere computationele complexiteit.
• Garantie op optimaliteit: Garandeert niet altijd dat de globale oplossing wordt gevonden. De garantie geldt alleen voor bepaalde probleemklassen.

Het wordt toegepast in problemen waarbij is bewezen dat de lokale optimale keuze bij elke stap leidt tot een globale optimale oplossing. Voorbeelden:

• Activiteitenselectieprobleem: Het kiezen van het maximale aantal niet-overlappende activiteiten in de tijd.
• Probleem van de rugzak (met fractionering van voorwerpen): Wanneer voorwerpen kunnen worden gedeeld. Anders is het een probleem van dynamische programmering.
• Prim- en Kruskal-algoritme: Voor het vinden van de minimale spanner in een graaf.
• Dijkstra-algoritme: Voor het vinden van de kortste weg in een graaf met niet-negatieve gewichten.
• Huffman-codering: Voor het bouwen van een optimale prefixcode.

Voorbeeld pseudocode voor het activiteitenselectie-algoritme:

Functie SelecteerActiviteiten(activiteiten):
  Sorteer activiteiten op eindtijd
  geselecteerde_activiteiten = lege lijst
  laatste_eindtijd = 0

  Voor elke activiteit in activiteiten:
    Als activiteit.starttijd >= laatste_eindtijd:
      Voeg activiteit toe aan geselecteerde_activiteiten
      laatste_eindtijd = activiteit.eindtijd

  Retourneer geselecteerde_activiteiten

Het is belangrijk om te controleren of het greedy-algoritme toepasbaar is op een specifiek probleem, omdat het anders een suboptimale oplossing kan geven.