Pohlepni algoritem naredi lokalno optimalno izbiro pri vsakem koraku, v upanju, da vodi do globalnega optimuma. Je preprost in hiter, a le pravilen, ko ima problem pohlepno-izbiro lastnost in optimalno podstrukturi.
Nikoli ne prerazmisli preteklih izbir — zavezani se k najboljši neposredni možnosti in nadaljuj.
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]
To je optimalno za ameriške kovance, vendar ne deluje za nabore kot {1, 3, 4}, kjer pohlepni daje 4+1+1 za 6 namesto 3+3.
Primeri, ki delujejo: Dijkstrin algoritem, Kruskalov/Primov (MST), Huffmanov kod, razporeditev intervalov.
Navadno hiter — pogosto O(n log n) po sortiranju.
Pohlepni ni vedno pravilen. Dokaži pohlepno-izbiro lastnost ali testiraj zoper brute-force/DP osnovo preden mu zaupam.
Ko je pohlepni primeren, je daleč enostavnejši in hitrejši od DP ali brute force.
Znanje kdaj je veljaven — in kdaj tiho daje napačne odgovore — je znak algoritmske zrelosti.
Mnogi temeljni grafovski algoritmi so v srcu pohlepni.
Knjižnica IT vprašanj za razgovore s podrobnimi odgovori — od začetnika do izkušenega.
Doniraj