Grådig algoritme
Fra Wikipedia, den frie encyklopedi
En grådig algoritme er en algoritme som hele tiden velger det som ser best ut i øyeblikket. For eksempel kan problemet med å gi tilbake vekslepenger løses med en grådig algoritme. For å gi tilbake færrest mulig mynter, er det best å hele tiden gi tilbake mynter med størst mulig verdi. 46 kr = 20 kr + 20 kr + 5 kr + 1 kr = 4 mynter.
Kjennetegnet for en grådig algoritme, er at det ikke går an å endre valgene som allerede er gjort. I eksempelet med vekslepenger, betyr det at algoritmen må velge å gi ut 20 kr, uten å vite om det finnes en god måte å gi ut de resterende 26 kr på.
Grådige algoritmer er som regel raske, men de gir ikke alltid riktig svar. Anta det finnes en mynt med verdien 16 kr. Da vil det være optimalt å gi tilbake 20 kr + 16 kr + 10 kr = 3 mynter. Dermed er det i mange tilfeller nødvendig å bruke dynamisk programmering for å kunne prøve ut flere forskjellige valg parallelt. Andre eksempler hvor grådige algoritmer er nyttige, er i en vektet graf å bruke Prims algoritme for å finne minste utspennede tre og Dijkstras algoritme for å finne korteste vei.
Ofte er det også nok å finne en god løsning, som ikke trenger å være optimal. Grådige algoritmer kan da ofte gi tilnærmingsløsninger på relativt kort tid.
