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