शुभ दिन, हेब्र! आज मैं लालची एल्गोरिदम के बारे में बात करना चाहूंगा।

कुछ समस्याओं को हल करने के लिए कई विधियाँ हैं: डायनेमिक प्रोग्रामिंग , एन्यूमरेशन । कोई कम प्रसिद्ध और काफी सामान्य लालची एल्गोरिदम नहीं हैं।

मुझे लगता है कि उसके जीवन में हर प्रोग्रामर ने कम से कम एक बार एक लालची लिखा, शायद इसके बारे में भी सोचे बिना। यह क्या है? बिल्ली के लिए आपका स्वागत है।

लालच वाइस नहीं है

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

वैसे, फ्लॉयड का एल्गोरिदम , जो एक ग्राफ में सबसे छोटे रास्तों की खोज करता है (हालांकि सभी कोने के बीच), लालची एल्गोरिथ्म का उदाहरण नहीं है। फ्लोयड एक अन्य विधि का प्रदर्शन करता है - गतिशील प्रोग्रामिंग विधि।

लालची एल्गोरिथ्म का उपयोग करना बहुत मानक है। इसे निम्न कार्य के उदाहरण के रूप में देखें:

कार्य निर्धारित करें

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

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

यह निम्नलिखित कोड को बताता है:

//tasks - Arrays.sort(tasks); // TreeSet<Integer> time = new TreeSet<Integer>(); for ( int i = 1; i <= n; ++i) { time.add(i); } int ans = 0; for ( int i = 0; i < n; ++i) { Integer tmp = time.floor(tasks[i].time); if (tmp == null ) { // , time.remove(time.last()); } else { // , time.remove(tmp); ans += tasks[i].cost; } }

तुम कब लालची हो सकते हो?

~~हमेशा।~~ कभी-कभी जहां भी संभव हो, लालची का उपयोग करने के लिए लुभावना हो सकता है, लेकिन कुछ कार्यों पर यह अस्वीकार्य है। उदाहरण के लिए, एक बैकपैक का कार्य : एक चोर ने एक गोदाम में अपना रास्ता बनाया, जिसमें तीन चीजें क्रमशः 10 किलो, 20 किलो और 30 किलो वजन की होती हैं और 60, 100 और 120 लकड़ी के सदाबहार नैनोरबल्स की लागत होती है। एक चोर अधिकतम 50 किलो वजन ले जा सकता है। चोर के लाभ को अधिकतम करना आवश्यक है। यदि आप लालच से काम करते हैं और सबसे मूल्यवान चीज चुनते हैं (यानी, पहले टुकड़े के प्रति 6 नैनोरबल्स, दूसरे के 5 नैनोरबल्स और तीसरे के 4 नैनोरबल्स प्रति किलो), तो चोर को किसी भी तरह से पहली चीज लेनी चाहिए, फिर दूसरी चीज के लिए जगह होगी। हालाँकि, इष्टतम समाधान दूसरी और तीसरी चीज़ है।

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

जीवन एक matroid नहीं है, जीवन एक परिमित ऑटोमेटन है!

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

सेट मैं nonempty है। यहां तक कि अगर मूल सेट एक्स खाली था - एक्स = X, तो मैं एक तत्व शामिल करूंगा - एक सेट जिसमें खाली है। मैं = {{=}}
सेट के किसी भी तत्व का कोई सबसेट मैं भी इस सेट का एक तत्व होगा।
यदि सेट A और B सेट I से संबंधित हैं, और यह भी ज्ञात है कि A का आकार B से कम है, तो B से कुछ तत्व x है जो A से संबंधित नहीं है, जैसे कि x और A का मिलन सेट I से संबंधित है। यह संपत्ति पूरी तरह से तुच्छ नहीं है। लेकिन सबसे अधिक अक्सर सभी दूसरों के सबसे महत्वपूर्ण।

यदि सेट पर एक्स में एडिटिव वेट फंक्शन w मौजूद हो तो मैट्रोइड को वेटेड कहा जाता है। सेट का वजन उसके तत्वों के वजन के योग के रूप में निर्धारित किया जाएगा।

आइए कार्यों के साथ एक फ्रीलांस प्रोग्रामर के ~~रूप में हमारे मेढ़ों पर~~ वापस जाएं। यहां आप निम्नलिखित मैट्रोइड देख सकते हैं: वाहक को बहुत सारे कार्य करने दें, और स्वतंत्र सेट - सफलतापूर्वक पूरा किए गए कार्य। प्रत्येक आवेदन का वजन इसकी लागत होगी। जाँच करें कि क्या यह जोड़ी एक चटाई है:

पहली संपत्ति स्पष्ट रूप से संतुष्ट है। भरे हुए कार्यों का एक खाली सेट हमारे सेट में शामिल है। खैर, इस बात की परवाह न करें कि वासना पैसा कमाना नहीं चाहती।
दूसरा सेट भी है। ऐसा क्यों है: बढ़ती समय सीमा के क्रम में सफलतापूर्वक पूर्ण किए गए कार्यों को क्रमबद्ध करें। इस क्रम में, वे अभी भी सफलतापूर्वक निष्पादित किए जाएंगे। इस क्रम में, यह स्पष्ट है कि सफलतापूर्वक पूर्ण किए गए कार्यों का कोई भी सबसेट सफलतापूर्वक पूरा हो जाएगा।
तीसरी संपत्ति, हालांकि स्पष्ट नहीं है, पूरी हो गई है। मान लीजिए कि हमारे पास सफलतापूर्वक पूर्ण किए गए कार्यों ए और बी के दो सेट हैं, और यह ज्ञात है कि | ए | <| बी | डिफ़ॉल्ट रूप से, हम दोनों सेटों में समय सीमा के बढ़ते क्रम में कार्यों को क्रमबद्ध करते हैं। बी से एक कार्य लें, जो ए में नहीं है, और इसे सेट ए में जोड़ने का प्रयास करें। हम सफल होंगे, क्योंकि यदि ए में कोई जगह नहीं थी, तो यह कार्य मौजूद होना चाहिए था।

मैं ऐसा क्यों कर रहा हूं? मैट्रोइड्स का पूरा आकर्षण राडो-एडमंड्स प्रमेय में निहित है: यदि आप साबित करते हैं कि ऑब्जेक्ट एक मैट्रोइड है, तो लालची एल्गोरिथ्म सही ढंग से काम करेगा और सही परिणाम देगा।

लालची एल्गोरिथ्म को ही इस तरह लागू किया जाता है:

// वजन के आधार पर छाँटें

// सबसे पहले, उत्तर एक खाली सेट है
के लिए

को

अगर

तब // यदि उपयुक्त हो

// फिर सेट में शामिल करें

संदर्भ

पुनश्च

वैसे, शेड्यूल की समस्या को O (n) में तेजी से हल किया जा सकता है। कौन कमजोर नहीं है? (संकेत: आपको ट्रीसेट को किसी अन्य संरचना से बदलने की आवश्यकता है)।

लालची