Gröniga algoritmer är en typ av algoritmisk strategi som gör det optimala valet vid varje steg med hopp om att hitta det globala optimala. De används ofta för att lösa optimeringsproblem där lokala beslut leder till en globalt optimal lösning. Denna artikel utforskar begreppet giriga algoritmer, ger praktiska exempel och visar hur man utför relaterade beräkningar.
Vad är Greedy Algorithms?
En girig algoritm bygger upp en lösning bit för bit, alltid välja nästa bit som erbjuder den mest omedelbara fördelen. Detta tillvägagångssätt är enkelt och effektivt men garanterar inte alltid den bästa övergripande lösningen för alla problem. Det är mest effektivt när problemet uppvisar girighetsvalet och optimal understruktur.
Praktiska exempel
Vanliga problem lösta med giriga algoritmer inkluderar myntbytesproblem, aktivitetsval och fraktionella knapsackproblem. Dessa exempel visar hur man gör lokalt optimala val kan leda till en globalt optimal lösning i specifika scenarier.
Beräkningar och genomförande
Tänk på myntbytesproblemet där målet är att göra förändring för ett visst belopp med de minsta mynten. Anta att myntbeteckningarna är 1, 5, 10 och 25 cent, och målbeloppet är 63 cent. Den giriga inställningen innebär att välja det största myntet mindre än eller lika med det återstående beloppet vid varje steg.
Steg-för-steg beräkning:
- Välj 25 cent (återstående: 63 - 25 = 38)
- Välj 25 cent (återstående: 38 - 25 = 13)
- Välj 10 cent (återstående: 13 - 10 = 3)
- Välj 1 cent (återstående: 3 - 1 = 2)
- Välj 1 cent (återstående: 2 - 1 = 1)
- Välj 1 cent (återstående: 1 - 1 = 0)
Totala mynt som används: 6.