एक लालची एल्गोरिथम प्रत्येक चरण पर स्थानीय रूप से सर्वोत्तम विकल्प बनाता है, आशा करता है कि यह वैश्विक इष्टतमता की ओर ले जाता है। यह सरल और तेज़ है, लेकिन केवल सही है जब समस्या में लालची-विकल्प संपत्ति और इष्टतम उप-संरचना हो।
पिछली पसंद पर कभी पुनर्विचार न करें — सर्वोत्तम तत्काल विकल्प पर ध्यान दें और आगे बढ़ें।
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) छँटाई के बाद।
लालची हमेशा सही नहीं होता है। लालची-विकल्प संपत्ति साबित करें या उस पर विश्वास करने से पहले brute-force/DP baseline के विरुद्ध परीक्षण करें।
जब लालची लागू होता है, तो यह DP या brute force की तुलना में कहीं अधिक सरल और तेज़ होता है।
कब यह मान्य है — और कब यह चुपचाप गलत उत्तर देता है — यह एल्गोरिथमिक परिपक्वता का एक संकेत है।
कई प्रमुख ग्राफ़ एल्गोरिथम मूल रूप से लालची हैं।