En grådig algoritme gjør det lokalt optimale valget ved hvert trinn, i håp om at det fører til en global optimum. Den er enkel og rask, men bare riktig når problemet har egenskapen grådige-valg og optimal delstruktur.
Aldri gjenoppta tidligere valg — forplikt deg til det beste umiddelbare alternativet 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 mynter, men mislykkes for sett som {1, 3, 4} der grådig gir 4+1+1 for 6 i stedet for 3+3.
Eksempler som fungerer: Dijkstra, Kruskal/Prim (MST), Huffman-koding, intervalplanlegging.
Vanligvis raskt — ofte O(n log n) etter sortering.
Grådig er ikke alltid riktig. Bevis egenskapen grådige-valg eller test mot en brute-force/DP baseline før du stoler på det.
Når grådig gjelder, er det langt enklere og raskere enn DP eller brute force.
Å vite når det er gyldig — og når det stille gir feil svar — er et tegn på algoritmisk modenhet.
Mange grunnleggende grafalgoritmene er grådige i hjertet.