Algorytm zachłanny dokonuje lokalnie optymalnego wyboru na każdym kroku, mając nadzieję, że prowadzi to do optimum globalnego. Jest prosty i szybki, ale tylko poprawny, gdy problem ma właściwość wyboru zachłannego i optymalną podstrukturę.
Nigdy nie przeanalizuj ponownie wcześniejszych wyborów — zobowiąż się do najlepszej opcji chwilowej i idź dalej.
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]
Jest to optymalne dla monet amerykańskich, ale zawodzi dla zbiorów takich jak {1, 3, 4}, gdzie zachłanność daje 4+1+1 dla 6 zamiast 3+3.
Przykłady, które działają: Dijkstra, Kruskal/Prim (MST), kodowanie Huffmana, planowanie interwałów.
Zwykle szybko — często O(n log n) po sortowaniu.
Zachłanność nie zawsze jest poprawna. Udowodnij właściwość wyboru zachłannego lub przetestuj względem baseline'a brute-force/DP, zanim zaufasz.
Gdy zachłanność się sprawdza, jest to znacznie prostsze i szybsze niż DP lub brute force.
Wiedza o tym, kiedy jest to ważne — i kiedy w cichy sposób daje błędne odpowiedzi — jest znakiem algorytmicznej dojrzałości.
Wiele fundamentalnych algorytmów grafowych ma zachłanność w sercu.