कम से कम बिजली खोजने के लिए एल्गोरिथ्म इसके सबसेट द्वारा निर्धारित एक परिमित कवर

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





एल्गोरिथ्म स्वयं दो कथनों और दो प्रमेयों पर आधारित है, जिसके प्रमाण यहां नहीं दिए गए हैं, क्योंकि उनकी बड़ी मात्रा है।



शुरू करने के लिए, हम यह निर्धारित करेंगे कि हम वास्तव में क्या देख रहे हैं।



एक परिमित सेट दिया जाए और परिवार इसके सबसेट ।

उपपरिवार का पता लगाएं (अगर यह मौजूद है) ऐसा और सबफ़ामिली एस * (सेट वी का कवर) की शक्ति सभी संभव में सबसे छोटी है।



निम्नलिखित कथन न्यूनतम और न्यूनतम कवरेज की अवधारणाओं को परिभाषित करते हैं।



कथन १

उपपरिवार को एक भीड़ का आवरण था , यह शर्त के लिए आवश्यक और पर्याप्त है





कवरिंग S 'को न्यूनतम कहा जाता है यदि कोई कवरिंग S' 'ऐसा नहीं है ।

किसी कवरिंग S * को कम से कम कहा जाता है अगर किसी भी न्यूनतम कवरिंग S 'कंडीशन के लिए





कथन २

कवरेज कम से कम अगर और केवल अगर किसी के लिए हालत

---

और, सबसे बुनियादी।



एक परिमित सेट दिया जाए और परिवार इसके सबसेट ।

हम एक पूर्ण लोड ग्राफ का निर्माण करते हैं जिसमें सेट है ग्राफ के कोने विशिष्ट रूप से परिवार के साथ जुड़े हुए हैं सबसेट ।

और प्रत्येक रिब के लिए - सबसेट ।



हम निरूपित करते हैं शीर्ष करने के लिए सभी किनारों घटना का सेट , और - सेट से किनारों पर सभी कोने की घटना का सेट ।



प्रमेय १

न्यूनतम बिजली उपसमुच्चय किनारों की घटना एक अनियंत्रित शीर्ष पर होती है कॉलम G में, शर्तों के तहत



न्यूनतम कवरेज निर्धारित करता है विशिष्ट रूप से सेट के अनुरूप कोने अगर , या कई कोने अगर ।



प्रमेय २

न्यूनतम बिजली उपसमुच्चय किनारों की घटना एक अनियंत्रित शीर्ष पर होती है रिब्स कॉलम G में, शर्तों के तहत



सभी के लिए

सबसे छोटी कवरेज निर्धारित करता है विशिष्ट रूप से सेट के अनुरूप कोने अगर , या कई कोने अगर ।

---

प्रमेयों के आधार पर, कम से कम कवरेज खोजने के लिए निम्नलिखित एल्गोरिदम प्रस्तावित है।



1. कई और परिवार इसके सबसेट मैच परिवार सबसेट । अगर कुछ के लिए होगा , फिर एक तुच्छ आवरण है । एल्गोरिथ्म का अंत।

अन्यथा, चरण 2 पर जाएं।



2. एक पूर्ण लोड ग्राफ का निर्माण जहाँ ।

चोटी बहुत लोड करें

रिब बहुत लोड करें ।



3. कवरेज के अस्तित्व की जाँच करें: एक मनमाना शीर्ष के लिए एक सबसेट परिभाषित करें

।

जहाँ - शीर्ष पर कई किनारों की घटना ग्राफ में ।

अगर फिर कवरेज मौजूद नहीं है। एल्गोरिथ्म का अंत।

अगर फिर कवरेज मौजूद है। सबसे छोटी कवरेज (खंड 4) खोजने के लिए प्रक्रिया पर जाएं।



4. टी लगाएं: = 0।

5. भरी हुई कॉलम में पसली जिसके लिए शर्त पूरी की जाती है ।

अगर फिर चरण 6 पर जाएं,

अन्यथा, डी कवरेज के सेट के निर्माण की प्रक्रिया पर सबसे छोटी कवरेज को परिभाषित करता है (पैराग्राफ 7)।



6. एक पूर्ण भरी हुई ग्राफ़ बनाएँ विश्वास । - शीर्ष पर कई किनारों की घटना ग्राफ में ।

लगाना सभी के लिए ।

टी लगाएं: = टी + 1 और चरण 5 पर जाएं।



7. सबसे छोटे कवरेज को परिभाषित करने वाले सेट डी के सेट की शुरुआत ।

लगाना ।



8. यदि t = 0 है, तो चरण 11 पर जाएं, अन्यथा, t: = t-1 डालें।



9. कॉलम में एक सबसेट परिभाषित करें



10. यदि कॉलम में हालत संतुष्ट है फिर डाल दिया अन्यथा - डी: = डी। चरण 8 पर जाएं।



11. परिवार सबसेट सेट की सबसे छोटी कवरेज को परिभाषित करता है ।

एल्गोरिथ्म का अंत।

---

आइए एल्गोरिथ्म की जटिलता का मूल्यांकन करने का प्रयास करें।

एल्गोरिथ्म का पूरा सार, इसलिए बोलना (जटिलता मूल्यांकन के दृष्टिकोण से) वाक्यांश में निहित है "हम एक पूर्ण लोड ग्राफ का निर्माण करेंगे"।

हमें ग्राफ के किनारों के भार के लिए ग्राफ के n कोने और (n-1) n / 2 गणना (पूर्ण ग्राफ़ के किनारों की संख्या द्वारा) पर लोड की गणना करने के लिए n क्रियाएं करने की आवश्यकता है। और यह सब, अगर हम सबसे खराब स्थिति पर विचार करते हैं, जब सबसेट नहीं काटते हैं, तो इसे n-2 बार किया जाता है। इस प्रकार, एक मोटा अनुमान O (n) = n ³ + n ^{2 है} ।



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

यूनानियों ने वहाँ क्या कहा? - Fais se que dois adviegne que peut (जो करना चाहिए और जो होना चाहिए) करें।

(या वे रोमन थे?)