आपकी समस्या का एक हिस्सा है "लालची समस्याओं" के बारे में सोचकर हो सकता है। लालची एल्गोरिदम और समस्याएं हैं जहां एक लालची एल्गोरिदम है, जो एक इष्टतम समाधान की ओर जाता है। अन्य कठोर समस्याएं हैं जिन्हें लालची एल्गोरिदम द्वारा भी हल किया जा सकता है लेकिन परिणाम आवश्यक नहीं होगा।
उदाहरण के लिए, बिन पैकिंग समस्या के लिए, उनमें से कई लालची एल्गोरिदम हैं जो घातीय एल्गोरिदम की तुलना में बहुत बेहतर जटिलता के साथ हैं, लेकिन आप केवल यह सुनिश्चित कर सकते हैं कि आपको एक निश्चित थ्रेसहोल्ड की तुलना में एक समाधान मिलेगा इष्टतम समाधान के लिए।
केवल उन समस्याओं के बारे में जहां लालची एल्गोरिदम एक इष्टतम समाधान का कारण बनेंगे, मेरा अनुमान होगा कि एक अपरिवर्तनीय शुद्धता प्रमाण पूरी तरह से प्राकृतिक और आसान महसूस करता है। अपने लालची कदमों में से प्रत्येक के लिए, यह स्पष्ट है कि यह करने के लिए सबसे अच्छी बात थी।
आमतौर पर इष्टतम, लालची समाधान के साथ समस्याएं आसान होती हैं, और अन्य जटिलता सीमाओं के कारण आपको लालची ह्युरिस्टिक के साथ आने के लिए मजबूर करेंगे। आम तौर पर एक सार्थक कमी यह दिखाती है कि आपकी समस्या वास्तव में कम से कम एनपी-हार्ड है और इसलिए आपको पता है कि आपको एक ह्युरिस्टिक खोजना होगा। उन समस्याओं के लिए, मैं कोशिश करने का एक बड़ा प्रशंसक हूं।अपने एल्गोरिदम को कार्यान्वित करें और यह पता लगाने का प्रयास करें कि क्या समाधान "बहुत अच्छे" हैं (आदर्श यदि आपके पास धीमा लेकिन सही एल्गोरिदम भी है, तो आप परिणामों की तुलना कर सकते हैं, अन्यथा आपको मैन्युअल रूप से ग्राउंड सच्चाई बनाने की आवश्यकता हो सकती है)। केवल तभी यदि आपके पास कुछ अच्छा काम करता है, तो सोचने की कोशिश करें कि क्यों और शायद सीमाओं के सबूत के साथ आने का प्रयास करें। शायद यह काम करता है, हो सकता है कि आप सीमावर्ती मामलों को खोज सकें जहां यह काम नहीं करता है और परिशोधन की आवश्यकता है।
स्रोत
2011-10-25 10:56:28
मुझे लगता है कि आप का मतलब है" matroid संपत्ति "और नहीं "मोनोइड प्रॉपर्टी"। क्या आप "इष्टतम सबस्ट्रक्चर" प्रॉपर्टी पर भी अधिक विशिष्ट हो सकते हैं? मैं इस संपत्ति को गतिशील प्रोग्रामिंग से जानता हूं, जहां आप अपनी समस्या को कई उपप्रोबल में विघटित करते हैं और फिर उन्हें पुनः संयोजित करते हैं। हालांकि उदाहरण के लिए न्यूनतम स्पैनिंग पेड़ को देखते हुए मेरे पास है एक कठोर समय यह देखकर कि समानता कैसे है, क्योंकि एल्गोरिदम हमेशा पिछले समाधान में जोड़ता रहता है। – LiKao
आप सही हैं, निश्चित रूप से मेरा मतलब मैट्रॉइड था। यदि आप किनारों को हटाने के रूप में समस्या को देखते हैं तो एमएसटी सबस्टक्चर देखा जा सकता है और शेष ग्राफ को पहले से ही शामिल किए गए कोष्ठकों के सेट पर कनेक्ट करना है। – Frank