Art gallery problem
आर्ट गैलरी समस्या या संग्रहालय समस्या कम्प्यूटेशनल ज्यामिति में एक अच्छी तरह से अध्ययन की गई दृश्यता समस्या है। यह निम्नलिखित वास्तविक दुनिया की समस्या से उत्पन्न होता हैः "एक आर्ट गैलरी में, गार्ड की न्यूनतम संख्या क्या है जो एक साथ पूरी गैलरी का निरीक्षण कर सकते हैं?" समस्या के ज्यामितीय संस्करण में, कला दीर्घा के लेआउट को एक साधारण बहुभुज द्वारा दर्शाया जाता है और प्रत्येक रक्षक को बहुभुज में एक बिंदु द्वारा दर्शाया जाता है। बिंदुओं के एक समूह को एक बहुभुज की रक्षा करने के लिए कहा जाता है, यदि बहुभुज में प्रत्येक बिंदु के लिए, कुछ ऐसा है कि और के बीच का रेखा खंड बहुभुज को नहीं छोड़ता है। आर्ट गैलरी समस्या को रोबोटिक्स जैसे कई क्षेत्रों में लागू किया जा सकता है, जब कृत्रिम बुद्धिमत्ता (ए. आई.) को अपने परिवेश के आधार पर आंदोलनों को निष्पादित करने की आवश्यकता होती है। अन्य क्षेत्र, जहाँ इस समस्या को लागू किया जाता है, वे हैं छवि संपादन, एक चरण की प्रकाश समस्याएं या प्राकृतिक आपदाओं की चेतावनी के लिए बुनियादी ढांचे की स्थापना। मूल समस्या में कई भिन्नताएँ हैं जिन्हें आर्ट गैलरी समस्या भी कहा जाता है। कुछ संस्करणों में गार्ड परिधि, या यहां तक कि बहुभुज के शीर्षों तक ही सीमित होते हैं। कुछ संस्करणों में केवल परिधि या परिधि के एक उपसमुच्चय को संरक्षित करने की आवश्यकता होती है। उस संस्करण को हल करना जिसमें गार्ड को शीर्षों पर रखा जाना चाहिए और केवल शीर्षों को संरक्षित करने की आवश्यकता है, बहुभुज के दृश्यता ग्राफ पर हावी सेट समस्या को हल करने के बराबर है। चावताल की कला दीर्घा प्रमेय चावताल की कला दीर्घा प्रमेय, जिसका नाम वक्लाव चावताल के नाम पर रखा गया है, गार्ड की न्यूनतम संख्या पर एक ऊपरी सीमा देता है। इसमें कहा गया हैः "शीर्षों के साथ एक साधारण बहुभुज की रक्षा के लिए, गार्ड हमेशा पर्याप्त होते हैं और कभी-कभी आवश्यक होते हैं।" इतिहास इस बारे में सवाल कि कितने शीर्ष/पहरेदार/गार्ड की आवश्यकता थी, 1973 में विक्टर क्ली द्वारा चावताल के सामने रखा गया था। इसके तुरंत बाद चावताल ने इसे साबित कर दिया। चावताल के प्रमाण को बाद में स्टीव फिस्क द्वारा 3-रंगीन तर्क के माध्यम से सरल बनाया गया था। चावताल में अधिक ज्यामितीय दृष्टिकोण है, जबकि फिस्क ग्राफ सिद्धांत से प्रसिद्ध परिणामों का उपयोग करता है। फिस्क का संक्षिप्त प्रमाण स्टीव फिस्क का प्रमाण इतना छोटा और सुरुचिपूर्ण है कि इसे पुस्तक के प्रमाण में शामिल करने के लिए चुना गया था। प्रमाण इस प्रकार हैः सबसे पहले, बहुभुज त्रिभुज है (अतिरिक्त शीर्ष जोड़े बिना), जो संभव है, क्योंकि त्रिभुज का अस्तित्व कुछ सत्यापित स्थितियों में साबित होता है। परिणामी त्रिभुज ग्राफ के शीर्ष 3-रंगीन हो सकते हैं। स्पष्ट रूप से, 3-रंग के तहत, प्रत्येक त्रिभुज में तीनों रंग होने चाहिए। किसी भी एक रंग के शीर्ष एक वैध रक्षक समूह बनाते हैं, क्योंकि बहुभुज का प्रत्येक त्रिभुज उस रंग के साथ अपने शीर्ष द्वारा संरक्षित होता है। चूंकि तीन रंग बहुभुज के एन शीर्षों को विभाजित करते हैं, इसलिए सबसे कम शीर्ष वाला रंग अधिकांश गार्ड के साथ एक वैध गार्ड सेट को परिभाषित करता है। प्रमाण का चित्रण प्रमाण को स्पष्ट करने के लिए, हम नीचे दिए गए बहुभुज पर विचार करते हैं। पहला कदम बहुभुज को त्रिभुज बनाना है (चित्र 1 देखें)। फिर, एक उचित रंग (चित्र 2) लगाया जाता है और देखा जाता है कि लाल, नीले और हरे शीर्ष हैं। सबसे कम शीर्षों वाला रंग नीला या लाल है, इस प्रकार बहुभुज को गार्ड द्वारा कवर किया जा सकता है (चित्र 3)। यह आर्ट गैलरी प्रमेय से सहमत है, क्योंकि बहुभुज में शीर्ष हैं, और। सामान्यीकरण च्वाटल की ऊपरी सीमा वैध रहती है यदि कोनों पर गार्ड के लिए प्रतिबंध को किसी भी बिंदु पर गार्ड के लिए ढीला कर दिया जाता है जो बहुभुज के बाहर नहीं होता है। मूल कला-गैलरी प्रमेय के कई अन्य सामान्यीकरण और विशेषज्ञताएँ हैं। उदाहरण के लिए, ऑर्थोगोनल बहुभुज के लिए, जिनके किनारे/दीवारें समकोण पर मिलती हैं, केवल गार्ड की आवश्यकता होती है। इस परिणाम के कम से कम तीन अलग-अलग प्रमाण हैं, जिनमें से कोई भी सरल नहीं हैः कान, क्लॉ और क्लेटमैन द्वारा; लुबीव द्वारा; और सैक और टौसेंट द्वारा। एक संबंधित समस्या एक मनमाने बहुभुज ("किले की समस्या") के बाहरी हिस्से को कवर करने के लिए गार्ड की संख्या के लिए पूछती हैः कभी-कभी आवश्यक होते हैं और हमेशा पर्याप्त होते हैं यदि गार्ड को बहुभुज की सीमा पर रखा जाता है, जबकि कभी-कभी आवश्यक होते हैं और हमेशा पर्याप्त होते हैं यदि गार्ड को बहुभुज के बाहरी हिस्से में कहीं भी रखा जाता है। दूसरे शब्दों में, अनंत बाहरी को सीमित आंतरिक की तुलना में कवर करना अधिक चुनौतीपूर्ण है। कम्प्यूटेशनल जटिलता आर्ट गैलरी समस्या के निर्णय समस्या संस्करणों में, एक को एक बहुभुज और एक संख्या k दोनों के इनपुट के रूप में दिया जाता है, और यह निर्धारित करना चाहिए कि बहुभुज को k या उससे कम गार्ड के साथ संरक्षित किया जा सकता है या नहीं। यह समस्या-पूर्ण है, जैसा कि वह संस्करण है जहाँ रक्षक बहुभुज के किनारों तक ही सीमित हैं। इसके अलावा, अधिकांश अन्य मानक विविधताएं (जैसे कि गार्ड स्थानों को शीर्षों तक सीमित करना) एनपी-हार्ड हैं। गार्ड की न्यूनतम संख्या के लिए सन्निकटन एल्गोरिदम के संबंध में, समस्या को ए. पी. एक्स-हार्ड साबित किया, जिसका अर्थ है कि यह संभावना नहीं है कि किसी निश्चित स्थिरांक से बेहतर कोई सन्निकटन अनुपात एक बहुपद समय सन्निकटन एल्गोरिदम द्वारा प्राप्त किया जा सकता है। यह दर्शाता है कि इनपुट बहुभुज को उत्तल उपक्षेत्रों में विभाजित करके और फिर समस्या को एक निर्धारित आवरण समस्या तक कम करके शीर्ष रक्षकों की न्यूनतम संख्या के लिए एक लघुगणक सन्निकटन प्राप्त किया जा सकता है। जैसा कि दिखाया गया है, एक आर्ट गैलरी समस्या से प्राप्त सेट प्रणाली ने वी. सी. आयाम को सीमित किया है, जो ε-नेट के आधार पर सेट कवर एल्गोरिदम के अनुप्रयोग की अनुमति देता है जिसका सन्निकटन अनुपात बहुभुज शीर्षों की संख्या के बजाय गार्ड की इष्टतम संख्या का लघुगणक है। अप्रतिबंधित गार्डों के लिए, संभावित गार्ड पदों की अनंत संख्या समस्या को और भी कठिन बना देती है। हालांकि गार्ड को एक महीन ग्रिड पर रखने के लिए प्रतिबंधित करके, कुछ हल्की अतिरिक्त धारणाओं के तहत एक अधिक जटिल लघुगणक सन्निकटन एल्गोरिदम प्राप्त किया जा सकता है, जैसा कि नीचे दिखाया गया है। हालांकि, कुशल एल्गोरिदम को अधिकांश शीर्ष रक्षकों के एक समूह को खोजने के लिए जाना जाता है, जो च्वाटल की ऊपरी सीमा से मेल खाते हैं। यह साबित हुआ कि इन गार्डों के लिए एक प्लेसमेंट की गणना ओ (एन लॉग एन) समय में सबसे खराब स्थिति में, एक विभाजन और विजय एल्गोरिथ्म के माध्यम से की जा सकती है। फिस्क के लघु प्रमाण और बर्नार्ड चेज़ेल के रैखिक समय समतल त्रिकोण एल्गोरिथ्म का उपयोग करके एक रैखिक समय एल्गोरिथ्म दिया। सरल बहुभुज जिनमें छेद नहीं होते हैं, उनके लिए शीर्ष और किनारे के रक्षकों के लिए एक स्थिर कारक सन्निकटन एल्गोरिदम के अस्तित्व का अनुमान घोष द्वारा लगाया गया था। घोष के अनुमान को शुरू में सरल बहुभुज के दो विशेष उप-वर्गों में शीर्ष रक्षकों के लिए सही दिखाया गया था। मोनोटोन बहुभुज और बहुभुज एक किनारे से कमजोर रूप से दिखाई देते हैं। एक सन्निकटन एल्गोरिथ्म प्रस्तुत किया जो बहुपद समय में एक मोनोटोन बहुभुज के लिए एक शीर्ष रक्षक सेट की गणना करता है जैसे कि रक्षक सेट का आकार शीर्ष रक्षकों की इष्टतम संख्या का अधिकतम 30 गुना हो। एक सन्निकटन एल्गोरिथ्म प्रस्तुत किया जो ओ (एन2) समय में एक सरल बहुभुज के लिए एक शीर्ष रक्षक सेट की गणना करता है जो एक किनारे से कमजोर रूप से दिखाई देता है जैसे कि गार्ड सेट का आकार शीर्ष रक्षकों की इष्टतम संख्या का अधिकतम 6 गुना हो। इसके बाद, शीर्ष रक्षक और किनारे रक्षक का उपयोग करके सामान्य सरल बहुभुज की रक्षा के लिए निरंतर कारक सन्निकटन एल्गोरिदम प्रस्तुत करके अनुमान को पूरी तरह से निपटाने का दावा किया गया। सरल बहुभुज के उपवर्ग की रक्षा करने वाले शीर्ष के लिए जो एक किनारे से कमजोर रूप से दिखाई देते हैं, एक बहुपद-समय सन्निकटन योजना प्रस्तावित की गई थी। वर्टेक्स गार्ड्स के लिए एक सटीक एल्गोरिथ्म प्रस्तावित किया गया था। लेखकों ने बहुभुज के कई वर्गों के साथ व्यापक कम्प्यूटेशनल प्रयोग किए जिससे पता चलता है कि हजारों शीर्षों से जुड़े उदाहरणों के लिए भी अपेक्षाकृत कम गणना समय में इष्टतम समाधान पाए जा सकते हैं। इन उदाहरणों के लिए इनपुट डेटा और इष्टतम समाधान डाउनलोड करने के लिए उपलब्ध हैं। तीन आयाम यदि एक संग्रहालय को तीन आयामों में एक बहुफलक के रूप में दर्शाया जाता है, तो प्रत्येक शीर्ष पर एक गार्ड लगाने से यह सुनिश्चित नहीं होगा कि पूरा संग्रहालय निगरानी में है। हालाँकि पॉलीहेड्रॉन की पूरी सतह का सर्वेक्षण किया जाएगा, लेकिन कुछ पॉलीहेड्रा के लिए आंतरिक भाग में ऐसे बिंदु हैं जो निगरानी में नहीं हो सकते हैं। आर्ट गैलरी समस्या के संभावित उपयोग परिदृश्य आर्ट गैलरी समस्या का उपयोग कई कैमरों को स्थापित करने के लिए किया जा सकता है जब इसका उद्देश्य कम से कम कैमरों का उपयोग करके कैमरों की दृष्टि से एक बड़े क्षेत्र को कवर करना है। यह भी देखें कि तारा बहुभुज के साथ एक आयताकार बहुभुज को कवर करना तारा के आकार का बहुभुज, बहुभुज का एक वर्ग जिसके लिए आर्ट गैलरी की समस्या को एकल गार्ड के साथ हल किया जा सकता है। रोशनी की समस्याः अगर दीवारों को प्रतिबिंबित किया जाता है तो क्या एक ही गार्ड पर्याप्त है? टिप्पणियाँ संदर्भ स्रोत। .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. कम्प्यूटेशनल ज्यामिति प्रमाणों वाले लेख-समस्याओं को कवर करने वाले बहुभुज