लोभी अल्गोरिदम प्रत्येक पायरीवर स्थानिकदृष्ट्या सर्वोत्तम निवड करतो, आशा करतो की हे जागतिक इष्टतमतेकडे नेले जाईल. हे सोपे आणि वेगवान आहे, परंतु केवळ तेव्हाच बरोबर आहे जेव्हा समस्येचे लोभी-निवड गुणधर्म आणि इष्टतम उप-संरचना आहेत.
पूर्वीच्या निवडीवर कधीही विचार करू नकोस — सर्वोत्तम तात्काळ पर्यायासाठी प्रतिबद्ध रहा आणि पुढे जा.
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, interval scheduling.
सामान्यतः वेगवान — अनेकदा क्रमवारी केल्यानंतर O(n log n).
लोभी नेहमी बरोबर नसतो. लोभी-निवड गुणधर्माचा पुरावा द्या किंवा त्यावर विश्वास ठेवण्यापूर्वी brute-force/DP मूलभूत विरुद्ध परीक्षा करा.
जेव्हा लोभी लागू होते, तेव्हा हे DP किंवा brute force पेक्षा बरेच सोपे आणि वेगवान असते.
त्याचे कधी वैध आहे हे जाणून घेणे — आणि कधी गोप्यपणे चुकीची उत्तरे देते — हे अल्गोरिदमिक परिपक्वतेचे चिन्ह आहे.
अनेक मूलभूत आलेख अल्गोरिदम हृदयामध्ये लोभी आहेत.