लालची एल्गोरिदम

लालची एल्गोरिद्म एक एल्गोरिद्म है जो प्रत्येक चरण पर इष्टतम (वर्तमान चरण के भीतर) वेरिएंट को इस उम्मीद में चुनता है कि अंतिम समाधान वैश्विक अर्थों में इष्टतम होगा।

छोटा उदाहरण:
मान लीजिए कि हमारे पास अलग-अलग मूल्यवर्ग के सिक्कों की असीमित संख्या है और हमें राशि S एकत्र करने की आवश्यकता है। आइए दो विशिष्ट मामलों पर विचार करें, जिनमें से प्रत्येक को हम लालची एल्गोरिदम के साथ हल करने का प्रयास करेंगे।
अर्थात्, हम निम्नानुसार कार्य करेंगे: प्रत्येक चरण पर हम उच्चतम मूल्यवर्ग का एक सिक्का लेंगे (चरण के भीतर सबसे अच्छा विकल्प), जो शेष राशि से अधिक नहीं होगा।

a) मान लें कि सिक्कों का मूल्य 1, 5 और 10 है, और S = 27 है।
1) 10 लें, S: 27 -> 17
2) 10 लें, S: 17 -> 7
3) लो 5, एस: 7 -> 2
4) 1, S: 2 -> 1
5) 1 लें, S: 1 -> 0
परिणामस्वरूप, उन्होंने पाँच सिक्कों की राशि अर्जित की। आप स्वतंत्र रूप से (उदाहरण के लिए, क्रूर बल) यह सुनिश्चित कर सकते हैं कि 4 सिक्कों या उससे कम के लिए आप 27 स्कोर नहीं कर पाएंगे।

b) मान लें कि सिक्कों का मूल्य 1, 5 और 7 है, और S = 24 है।
1) लो 7, एस: 24 -> 17
2) लो 7, एस: 17 -> 10
3) लो 7, एस: 10 -> 3
4) 1, S: 3 -> 2
5) 1 लें, S: 2 -> 1
6) लो 1, एस: 1 -> 0.
हमने छह सिक्कों के साथ स्कोर किया, लेकिन चार सिक्कों के साथ एस स्कोर कर सके - दो 7 के अंकित मूल्य के साथ और दो 5 के अंकित मूल्य के साथ।

जैसा कि उदाहरण से देखा जा सकता है, लालची एल्गोरिथम के साथ समस्याओं को हल करना हमेशा संभव नहीं होता है। लेकिन अगर यह समग्र इष्टतम उत्तर की ओर ले जाता है, तो यह आमतौर पर गतिशील प्रोग्रामिंग या अन्य विधियों का उपयोग करने से आसान होगा।