એક લોભી અલ્ગોરિધમ દરેક પગલે સ્થાનિક રીતે શ્રેષ્ઠ પસંદગી કરે છે, આશા રાખે છે કે તે વૈશ્વિક શ્રેષ્ઠતમ તરફ દોરી જાય છે. તે સરળ અને ઝડપી છે, પરંતુ ફક્ત ત્યારે જ સાચો છે જ્યારે સમસ્યા લોભી-પસંદગીની મિલકત અને શ્રેષ્ઠ સબસ્ટ્રક્ચર ધરાવે છે.
કદી ભૂતકાળની પસંદગીઓ પર પુનર્વિચાર ન કરો — તાત્કાલિક શ્રેષ્ઠ વિકલ્પ માટે પ્રતિબદ્ધ રહો અને આગળ વધો.
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]
હું યુ.એસ. સિક્કાઓ માટે શ્રેષ્ઠ છે, પરંતુ {1, 3, 4} જેવા સમૂહો માટે નિષ્ફળ થાય છે જ્યાં લોભી 6 માટે 4+1+1 આપે છે 3+3 ની જગાએ.
ઉદાહરણો કે જે કામ કરે છે: Dijkstra, Kruskal/Prim (MST), Huffman coding, ક્રમ શ્રેણી નિર્ધારણ.
સામાન્ય રીતે ઝડપી — સામાન્ય રીતે O(n log n) છટણી પછી.
લોભી હંમેશા સાચો નથી. લોભી-પસંદગીની મિલકત સાબિત કરો અથવા તેના પર વિશ્વાસ કરતા પહેલા બ્રુટ-ફોર્સ/DP બેસલાઇન સામે તેસ્ટ કરો.
જ્યારે લોભી લાગુ થાય છે, તેવો DP અથવા બ્રુટ ફોર્સ કરતાં ઘણો સરળ અને ઝડપી છે.
ક્યારે તે સાચો છે — અને ક્યારે તે બિનજાણતાં ખોટા જવાબો આપે છે તે જાણવું — અલ્ગોરિધમીક પરિપક્વતાનું ચિહ્ન છે.
ઘણા અર્ધશાસ્ત્રીય ગ્રાફ અલ્ગોરિધમ્સ હૃદયમાં લોભી છે.