En grrådig algoritme foretager det lokalt optimale valg ved hvert trin i håb om, at det fører til et globalt optimum. Den er enkel og hurtig, men kun korrekt når problemet har greedy-choice egenskab og optimal substruktur.
Genvurdér aldrig tidligere valg — forpligt dig til det bedste øjeblikkelige valg og gå videre.
def greedy_coins(amount, coins=(25, 10, 5, 1)):
result = []
for coin in coins: # largest first
while amount >= coin:
amount -= coin # take as many as possible
result.append(coin)
return result
greedy_coins(36) # -> [25, 10, 1]
Dette er optimalt for amerikanske mønter, men fejler for sæt som {1, 3, 4} hvor grådigt giver 4+1+1 for 6 i stedet for 3+3.
Eksempler der virker: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.
Gewalt hurtig — ofte O(n log n) efter sortering.
Grådigt er ikke altid korrekt. Bevis greedy-choice egenskaben eller test mod en brute-force/DP baseline før du stoler på det.
Når grådigt gælder, er det langt enklere og hurtigere end DP eller brute force.
At vide hvornår det er gyldigt — og hvornår det stille giver forkerte svar — er et tegn på algoritmisk modenhed.
Mange hjørnesten grafalgoritmer er grådige i hjertet.
Et bibliotek af IT-interviewspørgsmål med detaljerede svar — fra Junior til Senior.
Donér