Wat is een greedy algoritme en hoe wordt het toegepast bij het oplossen van problemen?

De greedy-algoritme is een heuristische aanpak waarbij bij elke stap de lokaal optimale beslissing wordt genomen in de hoop dat dit leidt tot een globaal optimale oplossing.

Toepassingen:

1. Activiteitenselectieprobleem:

   • Probleem: Kies het maximale aantal niet-overlappende intervallen uit een gegeven set.
   • Greedy-oplossing: Sorteer de intervallen op basis van toenemende eindtijd. Kies bij elke stap het interval met de kleinste eindtijd dat niet overlapt met de reeds gekozen intervallen.

   # Voorbeeld van activiteitenselectie
   # activities = [(start_time, end_time)]
   
   activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
   activities.sort(key=lambda x: x[1]) # Sorteren op eindtijd
   
   selected_activities = []
   last_finish_time = -1
   
   for activity in activities:
       if activity[0] >= last_finish_time:
           selected_activities.append(activity)
           last_finish_time = activity[1]
   
   print(selected_activities) # [ (1, 4), (5, 7), (8, 11), (12, 16) ]
   

2. Muntwisselprobleem (Coin Change Problem) voor canonieke muntensets:

   • Probleem: Geef een bepaald bedrag met het minimale aantal munten.
   • Greedy-oplossing: Gebruik zoveel mogelijk van de grootste munten, totdat het bedrag is uitbetaald. Dit werkt alleen voor bepaalde muntensets (bijvoorbeeld 1, 5, 10, 25).

   # Voorbeeld van muntwissel (voor canonieke munten)
   coins = [25, 10, 5, 1]
   amount = 67
   result = {}
   
   for coin in coins:
       while amount >= coin:
           result[coin] = result.get(coin, 0) + 1
           amount -= coin
   
   print(result) # {25: 2, 10: 1, 5: 1, 1: 2}
   

3. Kruskal's algoritme voor het vinden van de minimale op spanning staande boom:

   • Probleem: Vind een subset van de randen van een verbonden, gewogen, ongerichte graaf die alle knooppunten verbindt met de minimale som van gewichten.
   • Greedy-oplossing: Sorteer alle randen op gewicht in oplopende volgorde. Voeg randen toe in volgorde, zolang ze geen cyclus vormen met de reeds gekozen randen, totdat er n-1 randen zijn toegevoegd (waar n het aantal knooppunten is).

Greedy-algoritmen zijn eenvoudig te implementeren, maar vinden niet altijd de globale optimale oplossing voor arbitrary problemen. Voor sommige problemen (bijvoorbeeld muntwissel met arbitrary sets munten, het algemene rugzakprobleem) is de greedy-benadering niet optimaal. Om optimaliteit of een betere benadering te garanderen, kunnen dynamische programmering of andere methoden nodig zijn. Het is belangrijk om te controleren of de greedy-methode geschikt is voor het specifieke probleem voordat je deze toepast.