A mohó algoritmus minden lépésben a helyileg optimális választást teszi meg, remélve, hogy globális optimumhoz vezet. Egyszerű és gyors, de csak akkor helyes, ha a problémának megvan a mohó választás tulajdonsága és az optimális részstruktúrája.
Soha ne gondold újra a múltbeli választásokat — kötelezd el magad a legjobb azonnali opcióval és menj tovább.
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]
Ez optimális az amerikai érméhez, de kudarcot vall az olyan halmazoknál, mint {1, 3, 4}, ahol a mohó 4+1+1 ad 6-hoz ahelyett, hogy 3+3.
Példák, amelyek működnek: Dijkstra, Kruskal/Prim (MST), Huffman kódolás, intervallum ütemezés.
Gyorsan — gyakran O(n log n) rendezés után.
A mohó nem mindig helyes. Bizonyítsd be a mohó választás tulajdonságát, vagy tesztelj brute-force/DP alapvonallal, mielőtt rábízod magad.
Ha a mohó alkalmazható, ez sokkal egyszerűbb és gyorsabb, mint a DP vagy brute force.
Annak ismerete, hogy mikor érvényes — és mikor hallgatagon ad rossz választ — az algoritmikus érettség jele.
Sok sarokpont gráf algoritmus mohó szívében.