यह एक लालची एल्गोरिदम क्यों है?

Question

मैं अपने पाठ्य पुस्तक में यह सवाल है:।

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

और जवाब यहाँ दिया जाता है:। http://mitpress.mit.edu/algorithms/solutions/chap16-solutions.pdf

(एफआईआर समाधान)

और मेरा जवाब है, एल्गोरिदम एक लालची एल्गोरिदम क्यों है?

मुझे लगता है कि ऐसा इसलिए है क्योंकि यह (लालची?) पसंद करता है कि आप हमेशा एक गतिविधि लेते हैं और इसे एक व्याख्यान कक्ष में डालते हैं, जहां गतिविधि को रखने के बजाय पहले से ही एक या अधिक गतिविधियां (यदि संभव हो) एक नए खाली व्याख्यान हॉल में। किंतु मुझे यकीन नहीं है। :)

Answer 1

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

Answer 2

ऐसा इसलिए है क्योंकि आप बाकी समस्या पर विचार करने से पहले व्याख्यान कक्ष 1 के साथ सबसे अधिक करते हैं। इस अर्थ में, व्याख्यान कक्ष 1 "लालची" है।

Answer 3

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

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

Answer 4

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