Grådig algoritme

En grådig algoritme er en algoritme som hele tiden vælger det som ser bedst ud i øjeblikket. For eksempel kan problemet med at give byttepenge tilbage løses med en grådig algoritme. For at give færrest muligt mønter tilbage, er det bedst at hele tiden give mønter med størst mulig værdi retur. 46 kr. = 20 kr. + 20 kr. + 5 kr. + 1 kr. = 4 mønter.

Eksempel på en grådig algoritme, der beregner hvilke mønter, der skal bruges til t betale 36 kr.

Kendetegnet for en grådig algoritme, er at det ikke er muligt at ændre de allerede foretagne valg. I eksemplet med byttepenge, betyder det at algoritmen må vælge at give 20 kr., uden at vide om der findes en god måde at give de resterende 26 kr. på.

Grådige algoritmer er generelt hurtige, men giver ikke altid den rigtige løsning. Antag, at der findes en mønt med en værdi af 16 kr. I så fald vil den optimale tilbagelevering af byttepenge være 20 kr. + 16 kr. + 10 kr. = 3 mønter. Dermed er det i mange tilfælde nødvendigt at bruge dynamisk programmering for at kunne afprøve flere forskellige muligheder parallelt.

Andre eksempler hvor grådige algoritmer er nyttige, er i en vægtet graf at bruge Prims algoritme for at finde mindste udspændende træ og Dijkstras algoritme for at finde korteste vej.

Ofte er det også nok at finde en god løsning, som ikke behøver at være optimal. Grådige algoritmer kan da ofte give tilnærmelsesvise løsninger på relativt kort tid.