ग्रीडी एल्गोरिथम

Error creating thumbnail:

लालची एल्गोरिदम परिवर्तन करते समय सिक्कों की न्यूनतम संख्या निर्धारित करते हैं। ये वे कदम हैं जो ज्यादातर लोग केवल {1, 5, 10, 20} मूल्यों वाले सिक्कों का उपयोग करके 36 सेंट का प्रतिनिधित्व करने के लिए लालची एल्गोरिथ्म का अनुकरण करने के लिए उठाएंगे। उच्चतम मूल्य का सिक्का, बकाया परिवर्तन से कम, स्थानीय इष्टतम है। (सामान्य तौर पर, परिवर्तन करने वाली समस्या को इष्टतम समाधान खोजने के लिए गतिशील प्रोग्रामिंग की आवश्यकता होती है, हालांकि, अधिकांश मुद्रा प्रणालियां विशेष मामले हैं जहां लालची रणनीति इष्टतम समाधान ढूंढती है।)

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

उदाहरण के लिए, ट्रैवलिंग सेल्समैन की समस्या (जो उच्च कम्प्यूटेशनल जटिलता की है) के लिए लालची रणनीति निम्नलिखित हेयुरिस्टिक है: यात्रा के प्रत्येक चरण पर, निकटतम अनजान शहर का दौरा करें। यह अनुमानी सर्वोत्तम समाधान खोजने का इरादा नहीं रखता है, लेकिन यह उचित संख्या में चरणों में समाप्त होता है; ऐसी जटिल समस्या का इष्टतम समाधान खोजने के लिए आम तौर पर अनुचित रूप से कई चरणों की आवश्यकता होती है। गणितीय अनुकूलन में, लालची एल्गोरिदम matroid के गुणों वाले संयोजी समस्याओं को बेहतर ढंग से हल करते हैं और सबमॉड्यूलर संरचना के साथ अनुकूलन समस्याओं के लिए निरंतर-कारक सन्निकटन देते हैं।

विशिष्टता

लालची एल्गोरिदम कुछ गणितीय समस्याओं पर अच्छा समाधान उत्पन्न करते हैं, लेकिन दूसरों पर नहीं। जिन समस्याओं के लिए वे काम करते हैं उनमें से अधिकांश में दो गुण होंगे:

लालची पसंद संपत्ति

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

इष्टतम उपसंरचना: यदि समस्या के इष्टतम समाधान में उप-समस्याओं के लिए इष्टतम समाधान शामिल हैं, तो समस्या इष्टतम उपसंरचना प्रदर्शित करती है।

विफलता के मामले

Examples on how a greedy algorithm may fail to achieve the optimal solution.

File:Greedy Glouton.svg

Starting from A, a greedy algorithm that tries to find the maximum by following the greatest slope will find the local maximum at "m", oblivious to the global maximum at "M".

File:Greedy-search-path-example.gif

To reach the largest sum, at each step, the greedy algorithm will choose what appears to be the optimal immediate choice, so it will choose 12 instead of 3 at the second step, and will not reach the best solution, which contains 99.

लालची एल्गोरिदम कई अन्य समस्याओं के लिए इष्टतम समाधान का उत्पादन करने में विफल रहता है और यहां तक ​​कि अद्वितीय सबसे खराब संभव समाधान भी उत्पन्न कर सकता है। उदाहरण ऊपर उल्लिखित ट्रैवलिंग सेल्समैन समस्या है: शहरों की प्रत्येक संख्या के लिए, शहरों के बीच दूरियों का असाइनमेंट होता है, जिसके लिए निकटतम-पड़ोसी अनुमान अद्वितीय सबसे खराब संभव दौरे का उत्पादन करता है। अन्य संभावित उदाहरणों के लिए, क्षितिज प्रभाव देखें।

प्रकार

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

• शुद्ध लालची एल्गोरिदम
• ऑर्थोगोनल लालची एल्गोरिदम
• आराम से लालची एल्गोरिदम

सिद्धांत

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

• लालची एल्गोरिदम किन समस्याओं के लिए बेहतर प्रदर्शन करते हैं?
• लालची एल्गोरिदम किन समस्याओं के लिए लगभग इष्टतम समाधान की गारंटी देते हैं?
• लालची एल्गोरिथम किन समस्याओं के लिए इष्टतम समाधान नहीं बनाने की गारंटी देता है?

सामान्य वर्ग की समस्याओं, जैसे मैट्रोइड्स, साथ ही सेट कवर जैसी विशिष्ट समस्याओं के लिए इन प्रश्नों का उत्तर देने के लिए साहित्य का बड़ा निकाय मौजूद है।

मैट्रोइड्स

Main article: Matroid

एक मैट्रॉइड गणितीय संरचना है जो वेक्टर रिक्त स्थान से मनमानी सेट तक रैखिक स्वतंत्रता की धारणा को सामान्यीकृत करती है। यदि अनुकूलन समस्या में मैट्रोइड की संरचना होती है, तो उचित लालची एल्गोरिदम इसे बेहतर तरीके से हल करेगा।

सबमॉड्यूलर फ़ंक्शन

Main article: Submodular set function § Optimization problems

एक समारोह $f$ सेट के सबसेट पर परिभाषित $\Omega$ सबमॉड्यूलर कहा जाता है अगर हर के लिए $S,T\subseteq \Omega$ हमारे पास वह है $f(S)+f(T)\geq f(S\cup T)+f(S\cap T)$.

मान लीजिए कोई समुच्चय खोजना चाहता है $S$ जो अधिकतम करता है $f$. लालची एल्गोरिदम, जो सेट बनाता है $S$ वृद्धिशील तत्व को जोड़कर जो बढ़ता है $f$ प्रत्येक चरण में सबसे अधिक, आउटपुट के रूप में सेट का उत्पादन करता है जो कम से कम है $(1-1/e)\max _{X\subseteq \Omega }f(X)$. अर्थात्, लालची स्थिर कारक के भीतर प्रदर्शन करता है $(1-1/e)\approx 0.63$ इष्टतम समाधान के रूप में अच्छा।

इसी तरह की गारंटी तब दी जा सकती है जब अतिरिक्त बाधाएं, जैसे कि कार्डिनैलिटी की कमी, आउटपुट पर लगाए जाते हैं, हालांकि लालची एल्गोरिथम पर अक्सर मामूली बदलाव की आवश्यकता होती है। देखना सिंहावलोकन के लिए।

गारंटी के साथ अन्य समस्याएं

अन्य समस्याएं जिनके लिए लालची एल्गोरिथ्म मजबूत गारंटी देता है, लेकिन इष्टतम समाधान नहीं है, इसमें शामिल हैं

• सेट कवर समस्या # लालची एल्गोरिथ्म
• स्टेनर ट्री समस्या
• भार संतुलन (कंप्यूटिंग)
• स्वतंत्र सेट (ग्राफ सिद्धांत) # सन्निकटन एल्गोरिदम

इनमें से कई समस्याओं की मैचिंग निचली सीमाएं हैं; यानी, लालची एल्गोरिथ्म सबसे खराब स्थिति में गारंटी से बेहतर प्रदर्शन नहीं करता है।

अनुप्रयोग

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

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

लालची एल्गोरिदम नेटवर्क मार्ग में भी दिखाई देते हैं। लालची रूटिंग का उपयोग करते हुए, संदेश पड़ोसी नोड को भेजा जाता है जो गंतव्य के सबसे करीब होता है। नोड के स्थान (और इसलिए निकटता) की धारणा को उसके भौतिक स्थान द्वारा निर्धारित किया जा सकता है, जैसा कि तदर्थ नेटवर्क द्वारा उपयोग किए जाने वाले भौगोलिक रूटिंग में होता है। स्थान भी पूरी तरह से कृत्रिम निर्माण हो सकता है जैसे कि छोटे विश्व रूटिंग और वितरित हैश तालिका में।

उदाहरण

• गतिविधि चयन समस्या इस वर्ग की समस्याओं की विशेषता है, जहाँ लक्ष्य उन गतिविधियों की अधिकतम संख्या को चुनना है जो दूसरे से टकराती नहीं हैं।
• मैकिंटोश कंप्यूटर गेम क्रिस्टल क्वेस्ट में, यात्रा विक्रेता समस्या के समान फैशन में, उद्देश्य क्रिस्टल को इकट्ठा करना है। गेम में डेमो मोड है, जहां गेम प्रत्येक क्रिस्टल पर जाने के लिए लालची एल्गोरिदम का उपयोग करता है। कृत्रिम बुद्धि बाधाओं के लिए जिम्मेदार नहीं है, इसलिए डेमो मोड अक्सर जल्दी समाप्त हो जाता है।
• मिलान पीछा सिग्नल सन्निकटन पर लागू लालची एल्गोरिथम का उदाहरण है।
• एक लालची एल्गोरिद्म मालफट्टी हलकों के लिए इष्टतम समाधान ढूंढता है। मालफट्टी की दी गई त्रिकोण के भीतर तीन असम्बद्ध हलकों को खोजने की समस्या जो हलकों के कुल क्षेत्रफल को अधिकतम करती है; यह अनुमान लगाया गया है कि समान लालची एल्गोरिथम किसी भी मंडलियों के लिए इष्टतम है।
• हफ़मैन कोडिंग के दौरान हफमैन पेड़ बनाने के लिए लालची एल्गोरिदम का उपयोग किया जाता है जहां यह इष्टतम समाधान पाता है।
• निर्णय वृक्ष सीखना में, लालची एल्गोरिदम का आमतौर पर उपयोग किया जाता है, हालांकि उन्हें इष्टतम समाधान खोजने की गारंटी नहीं है।
  • इस तरह का लोकप्रिय एल्गोरिथम निर्णय ट्री निर्माण के लिए ID3 एल्गोरिथम है।
• दिज्क्स्ट्रा का एल्गोरिद्म और संबंधित Aए * खोज एल्गोरिदम ग्राफ खोज और सबसे छोटा पथ समस्या के लिए सत्यापित रूप से इष्टतम लालची एल्गोरिद्म हैं।
  • A* खोज सशर्त रूप से इष्टतम है, जिसके लिए स्वीकार्य अनुमान की आवश्यकता होती है जो पथ की लागतों का अधिक अनुमान नहीं लगाएगा।
• क्रुस्कल आईडी3 एल्गोरिथम और प्राइम का एल्गोरिथम दिए गए जुड़े ग्राफ के न्यूनतम फैले हुए पेड़ों के निर्माण के लिए लालची एल्गोरिदम हैं। वे हमेशा इष्टतम समाधान ढूंढते हैं, जो सामान्य रूप से अद्वितीय नहीं हो सकता है।

यह भी देखें

• सर्वश्रेष्ठ-पहली खोज
• मल्टी-आर्म्ड बैंडिट#सेमी-यूनिफ़ॉर्म स्ट्रैटेजी|एप्सिलॉन-लालची रणनीति
• मिस्र के अंशों के लिए लालची एल्गोरिथ्म
• लालची स्रोत
• पहाड़ी की चढ़ाई
• क्षितिज प्रभाव
• मैट्रॉइड

संदर्भ

स्रोत

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "16 Greedy Algorithms". एल्गोरिदम का परिचय. MIT Press. pp. 370–. ISBN 978-0-262-03293-3.
• Gutin, Gregory; Yeo, Anders; Zverovich, Alexey (2002). "ट्रैवलिंग सेल्समैन को लालची नहीं होना चाहिए: टीएसपी के लिए लालची-प्रकार के अनुमानों का प्रभुत्व विश्लेषण". Discrete Applied Mathematics. 117 (1–3): 81–86. doi:10.1016/S0166-218X(01)00195-0.
• Bang-Jensen, Jørgen; Gutin, Gregory; Yeo, Anders (2004). "जब लालची एल्गोरिथ्म विफल हो जाता है". Discrete Optimization. 1 (2): 121–127. doi:10.1016/j.disopt.2004.03.007.
• Bendall, Gareth; Margot, François (2006). "कॉम्बीनेटरियल समस्याओं का लालची प्रकार का प्रतिरोध". Discrete Optimization. 3 (4): 288–298. doi:10.1016/j.disopt.2006.03.001.
• Feige, U. (1998). "अनुमानित सेट कवर के लिए ln n की दहलीज" (PDF). Journal of the ACM. 45 (4): 634–652. doi:10.1145/285055.285059. S2CID 52827488. Archived (PDF) from the original on 2022-10-09.
• Nemhauser, G.; Wolsey, L.A.; Fisher, M.L. (1978). "सबमॉड्यूलर सेट फ़ंक्शंस को अधिकतम करने के लिए सन्निकटन का विश्लेषण- I". Mathematical Programming. 14 (1): 265–294. doi:10.1007/BF01588971. S2CID 206800425.
• Buchbinder, Niv; Feldman, Moran; Naor, Joseph (Seffi); Schwartz, Roy (2014). "Submodular maximization with cardinality constraints" (PDF). असतत एल्गोरिदम पर पच्चीसवीं वार्षिक एसीएम-सियाम संगोष्ठी की कार्यवाही. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611973402.106. ISBN 978-1-61197-340-2. Archived (PDF) from the original on 2022-10-09.
• Krause, A.; Golovin, D. (2014). "Submodular Function Maximization". In Bordeaux, L.; Hamadi, Y.; Kohli, P. (eds.). सुवाह्यता: कठिन समस्याओं के लिए व्यावहारिक दृष्टिकोण. Cambridge University Press. pp. 71–104. doi:10.1017/CBO9781139177801.004. ISBN 9781139177801.
• Papadimitriou, Christos H.; Steiglitz, Kenneth (1998). मिश्रित अनुकूलन: एल्गोरिदम और जटिलता. Dover.

बाहरी संबंध

• "Greedy algorithm", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Gift, Noah. "Python greedy coin example".

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

• Evolutionary algorithm
• Hill climbing
• Local search
• Simulated annealing
• Tabu search

| below =

• Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

• पहाड़ी की चढ़ाई
• स्थानीय खोज
• तैयार किए हुयी धातु पे पानी चढाने की कला
• तब्बू खोज

| below =* सॉफ्टवेयर

}}