इस ट्यूटोरियल में, आप सीखेंगे कि एक लालची एल्गोरिथ्म क्या है। इसके अलावा, आपको एक लालची दृष्टिकोण का एक उदाहरण मिलेगा।
एक लालची एल्गोरिथ्म इस समय उपलब्ध सबसे अच्छे विकल्प का चयन करके किसी समस्या को हल करने के लिए एक दृष्टिकोण है, भविष्य के परिणाम के बारे में चिंता किए बिना। दूसरे शब्दों में, स्थानीय स्तर पर सबसे अच्छे विकल्प का लक्ष्य वैश्विक स्तर पर सर्वोत्तम परिणाम देना है।
यह एल्गोरिथ्म सभी समस्याओं के लिए सबसे अच्छा विकल्प नहीं हो सकता है। यह कुछ मामलों में गलत परिणाम दे सकता है।
यह एल्गोरिथ्म कभी भी किए गए निर्णय को उलटने के लिए वापस नहीं जाता है। यह एल्गोरिथ्म एक टॉप-डाउन दृष्टिकोण में काम करता है।
इस एल्गोरिथ्म का मुख्य लाभ यह है:
- एल्गोरिथ्म का वर्णन करना आसान है ।
- यह एल्गोरिदम अन्य एल्गोरिदम की तुलना में बेहतर प्रदर्शन कर सकता है (लेकिन, सभी मामलों में नहीं)।
संभव समाधान
एक संभव समाधान वह है जो समस्या का इष्टतम समाधान प्रदान करता है।
लालची एल्गोरिथ्म
- शुरू करने के लिए, समाधान सेट (उत्तर युक्त) खाली है।
- प्रत्येक चरण में, एक आइटम को समाधान सेट में जोड़ा जाता है।
- यदि समाधान सेट संभव है, तो वर्तमान आइटम रखा जाता है।
- इसके अलावा, आइटम को अस्वीकार कर दिया जाता है और फिर कभी नहीं माना जाता है।
उदाहरण - लालची दृष्टिकोण
समस्या: आपको सबसे कम संभव संख्या में सिक्कों का उपयोग करके राशि में बदलाव करना होगा। राशि: $ 28 उपलब्ध सिक्के: $ 5 सिक्का $ 2 सिक्का $ 1 सिक्का
उपाय:
- एक रिक्त समाधान-सेट बनाएं = ()।
- सिक्के = (५, २, १)
- योग = ०
- जबकि राशि, 28, निम्नलिखित करें।
- ऐसे सिक्कों में से एक C C चुनें, जैसे कि योग + C <28।
- यदि C + योग> 28 है, तो कोई समाधान न लौटें।
- एल्स, राशि = योग + सी।
- C को समाधान-सेट में जोड़ें।
पहले 5 पुनरावृत्तियों तक, समाधान सेट में 5 $ 5 सिक्के शामिल हैं। उसके बाद, हमें 1 $ 2 का सिक्का और अंत में, 1 $ 1 का सिक्का मिलता है।
लालची एल्गोरिथ्म अनुप्रयोग
- चयन छांटना
- क्लेश समस्या
- न्यूनतम फैलाव वाला पेड़
- सिंगल-सोर्स शॉर्टेस्ट पाथ प्रॉब्लम
- नौकरी निर्धारण समस्या
- प्राइम की मिनिमल स्पैनिंग ट्री एलगोरिदम
- क्रुश्कल की मिनिमल स्पैनिंग ट्री एलगोरिदम
- दिज्क्स्ट्रा का मिनिमल स्पैनिंग ट्री एलगोरिदम
- हफमैन कोडिंग
- Ford-Fulkerson Algorithm
