Greedy algoritmus provádí lokálně optimální volbu v každém kroku s nadějí, že vede k globálnímu optimu. Je jednoduchý a rychlý, ale správný je pouze tehdy, když má problém vlastnost greedy-choice a optimální substrukturu.
Nikdy nezvažujte minulé volby — zavažte se nejlepší okamžitou možností a pokračujte.
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]
Toto je optimální pro americké mince, ale selhává pro sady jako {1, 3, 4}, kde greedy dává 4+1+1 pro 6 místo 3+3.
Příklady, které fungují: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.
Zwykle rychlé — často O(n log n) po třídění.
Greedy není vždy správný. Dokažte vlastnost greedy-choice nebo jej otestujte proti brute-force/DP baseline před tím, než se jej rozhodnete použít.
Když se greedy vztahuje, je to mnohem jednoduší a rychlejší než DP nebo brute force.
Vědět kdy je platný — a kdy tiše dává nesprávné odpovědi — je znakem algoritmické zralosti.
Mnohé základní grafové algoritmy jsou v srdci greedy.
Knihovna IT otázek k pohovoru s podrobnými odpověďmi — od Junior po Senior.
Přispět