Algoritmu greed jagħmel għażla lokalment ottimali f'kull pass, bi speranza li twassal għal optimu globali. Hija sempliċi u veloċi, iżda korrett biss meta l-problema għandha proprjetà greedy-choice u struttura ottimali.
Magħaddiesx tabbula għar-riċerka ta' għażliet antiki — iltiżam għall-aħjar għażla immedjata u mur quddiem.
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]
Dan huwa ottimali għal muniti tal-ISTATI, imma nuqqas għal settijiet bħal {1, 3, 4} fejn greed jagħti 4+1+1 għal 6 minflok 3+3.
Eżempji li jaħdmu: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.
Bħal regola veloċi — ħafna drabi O(n log n) wara s-sorting.
Greed mhux dejjem korrett. Ipprova l-proprjetà greedy-choice jew test kontra baseline brute-force/DP qabel ma takkwista filwaqt.
Meta greed tapplika, hija ħafna iktar sempliċi u veloċi minn DP jew brute force.
Il-għarfien meta huwa validu — u meta b'mod taċitu tagħti risposti ħamsin — hija sinjal ta' maturità algoritnika.
Bħala algoritmi grafiku fundamentali għandhom qalb greed.
Librerija ta' mistoqsijiet ta' intervisti tal-IT b'tweġibiet dettaljati — minn Junior sa Senior.
Iddona