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

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

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

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

विशिष्टता

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

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

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

विफलता के स्थिति

कैसे एक ग्रीडी कलन विधि इष्टतम समाधान प्राप्त करने में विफल हो सकता है, इसके उदाहरण।

A से प्रारंभ होकर, एक ग्रीडी कलन विधि जो सबसे बड़ी ढलान का पालन करके अधिकतम खोजने की प्रयास करता है, स्थानीय अधिकतम "M" पर मिलेगा, वैश्विक अधिकतम "M" से अपरिचित होगा।

सबसे बड़ी राशि तक पहुंचने के लिए, प्रत्येक चरण पर, ग्रीडी कलन विधि को वह चुनेगा जो इष्टतम तत्काल विकल्प प्रतीत होता है, इसलिए यह दूसरे चरण में 3 के बजाय 12 का चयन करेगा, और सबसे सही समाधान तक नहीं पहुंचेगा, जिसमें 99 सम्मिलित हैं।

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

अन्य संभावित उदाहरणों के लिए, क्षितिज प्रभाव देखें।

प्रकार

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

शुद्ध ग्रीडी कलन विधि
ऑर्थोगोनल ग्रीडी कलन विधि
निश्चिंत से ग्रीडी कलन विधि

सिद्धांत

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

ग्रीडी कलन विधि किन समस्याओं के लिए उत्तम प्रदर्शन करते हैं?
ग्रीडी कलन विधि किन समस्याओं के लिए लगभग इष्टतम समाधान की प्रत्याभूति देते हैं?
ग्रीडी कलन विधि किन समस्याओं के लिए इष्टतम समाधान नहीं बनाने की प्रत्याभूति देता है?

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

मैट्रोइड्स

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

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

समुच्चय $\Omega$ के उपसमुच्चय पर परिभाषित फलन $f$ को सबमॉड्यूलर कहा जाता है यदि प्रत्येक $S,T\subseteq \Omega$ के लिए हमारे पास वह $f(S)+f(T)\geq f(S\cup T)+f(S\cap T)$ है

मान लीजिए कि कोई ऐसा समुच्चय S ज्ञात करना चाहता है जो $f$ को अधिकतम करता है। . ग्रीडी कलन विधि, जो समुच्चय बनाता है $S$ वृद्धिशील तत्व को जोड़कर जो बढ़ता है $f$ प्रत्येक चरण में सबसे अधिक, आउटपुट के रूप में समुच्चय का उत्पादन करता है जो कम से कम है .^[6] अर्थात्, ग्रीडी

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

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

प्रत्याभूति के साथ अन्य समस्याएं

अन्य समस्याएं जिनके लिए ग्रीडी कलन विधि शक्तिशाली प्रत्याभूति देता है, किन्तु इष्टतम समाधान नहीं है इसमें सम्मिलित हैं

समुच्चय कवर समस्या या ग्रीडी कलन विधि
स्टेनर ट्री समस्या
भार संतुलन (कंप्यूटिंग)^[9]
स्वतंत्र समुच्चय (ग्राफ सिद्धांत) या सन्निकटन कलन विधि

इनमें से कई समस्याओं की तुलना निचली सीमाएं हैं; अर्थात, ग्रीडी कलन विधि सबसे व्यर्थ स्थिति में प्रत्याभूति से उत्तम प्रदर्शन नहीं करता है।

अनुप्रयोग

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

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

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

उदाहरण

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

यह भी देखें

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

संदर्भ

↑ Black, Paul E. (2 February 2005). "लालची एल्गोरिदम". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology (NIST). Retrieved 17 August 2012.
↑ Cormen et al. 2001, Ch. 16
↑ Gutin, Gregory; Yeo, Anders; Zverovich, Alexey (2002). "Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP". Discrete Applied Mathematics. 117 (1–3): 81–86. doi:10.1016/S0166-218X(01)00195-0.
↑ Feige 1998
↑ Papadimitriou & Steiglitz 1998
↑ Nemhauser, Wolsey & Fisher 1978
↑ Buchbinder et al. 2014
↑ Krause & Golovin 2014
↑ "Lecture 5: Introduction to Approximation Algorithms" (PDF). Advanced Algorithms (2IL45) — Course Notes. TU Eindhoven. Archived (PDF) from the original on 2022-10-09.

स्रोत

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".

[NISTg-1] Black, Paul E. (2 February 2005). "लालची एल्गोरिदम". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology (NIST). Retrieved 17 August 2012.

[2] Cormen et al. 2001, Ch. 16

[3] Gutin, Gregory; Yeo, Anders; Zverovich, Alexey (2002). "Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP". Discrete Applied Mathematics. 117 (1–3): 81–86. doi:10.1016/S0166-218X(01)00195-0.

[4] Feige 1998

[5] Papadimitriou & Steiglitz 1998

[6] Nemhauser, Wolsey & Fisher 1978

[7] Buchbinder et al. 2014

[8] Krause & Golovin 2014

[9] "Lecture 5: Introduction to Approximation Algorithms" (PDF). Advanced Algorithms (2IL45) — Course Notes. TU Eindhoven. Archived (PDF) from the original on 2022-10-09.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]