आच्छादित समस्याएं: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Type of computational problem}} | {{Short description|Type of computational problem}} | ||
[[साहचर्य]] और [[ कंप्यूटर विज्ञान |कंप्यूटर विज्ञान]] में, '''समस्याओं को आच्छादित करना''' कम्प्यूटेशनल समस्याएं हैं जो पूछती हैं कि क्या एक निश्चित सांयोगिक संरचना दूसरे को 'आच्छादित' करता है, या ऐसा करने के लिए संरचना कितनी बड़ी होनी चाहिए। | [[साहचर्य]] और [[ कंप्यूटर विज्ञान |कंप्यूटर विज्ञान]] में, '''समस्याओं को आच्छादित करना''' कम्प्यूटेशनल समस्याएं हैं जो पूछती हैं कि क्या एक निश्चित सांयोगिक संरचना दूसरे को 'आच्छादित' करता है, या ऐसा करने के लिए संरचना कितनी बड़ी होनी चाहिए। आच्छादन समस्याएं [[अनुकूलन (गणित)|न्यूनीकरण (गणित)]] की समस्याएँ हैं और सामान्य रूप से [[पूर्णांक रैखिक कार्यक्रम|पूर्णांक रैखिक प्रोग्राम]] हैं, जिनकी [[दोहरी समस्या]]ओं को पैकिंग समस्याएं कहा जाता है। | ||
आच्छादन (कवरिंग) समस्याओं का सबसे प्रमुख उदाहरण समुच्चय आच्छादित समस्या है, जो अघाती समुच्चय समस्या के बराबर है, और इसके विशेष स्थिति मे, शीर्ष आच्छादित समस्या और कोर आच्छादित समस्या है। | |||
{{Covering-Packing_Problem_Pairs}} | {{Covering-Packing_Problem_Pairs}} | ||
== सामान्य [[रैखिक प्रोग्रामिंग]] सूत्रीकरण == | == सामान्य [[रैखिक प्रोग्रामिंग]] सूत्रीकरण == | ||
रैखिक प्रोग्रामिंग के संदर्भ में, किसी भी रैखिक प्रोग्राम को एक | रैखिक प्रोग्रामिंग के संदर्भ में, किसी भी रैखिक प्रोग्राम को एक आच्छादन समस्या के रूप में विचार कर सकते हैं यदि प्रतिबंध [[मैट्रिक्स (गणित)|आव्यूह (गणित)]], उद्देश्य फलन, और दक्षिणावर्ती पक्ष की ओर गुणांक गैर-ऋणात्मक हैं।<ref>{{Cite book | last=Vazirani | first=Vijay V. | author-link=Vijay Vazirani | title=सन्निकटन एल्गोरिदम| year=2001 | publisher=Springer-Verlag | isbn=3-540-65367-8 }}{{rp|112}} | ||
</ref> अधिक परिशुद्ध रूप से, निम्नलिखित सामान्य [[पूर्णांक रैखिक कार्यक्रम|पूर्णांक रैखिक प्रोग्राम]] पर विचार करें: | </ref> अधिक परिशुद्ध रूप से, निम्नलिखित सामान्य [[पूर्णांक रैखिक कार्यक्रम|पूर्णांक रैखिक प्रोग्राम]] पर विचार करें: | ||
{| | {| | ||
| Line 19: | Line 19: | ||
| <math>x_i \in \left\{0, 1, 2, \ldots\right\}\text{ for }i=1,\dots,n</math>. | | <math>x_i \in \left\{0, 1, 2, \ldots\right\}\text{ for }i=1,\dots,n</math>. | ||
|} | |} | ||
इस तरह के एक पूर्णांक रैखिक प्रोग्राम को | इस तरह के एक पूर्णांक रैखिक प्रोग्राम को आच्छादन समस्या कहा जाता है यदि <math>a_{ji}, b_j, c_i \geq 0</math> सभी के लिए <math>i=1,\dots,n</math> और <math>j=1,\dots,m</math>. | ||
'''अंतर्ज्ञान''': मान लीजिए <math>n</math> प्रकार की वस्तु है और प्रत्येक प्रकार की वस्तु <math>i</math> की संबद्ध कीमत <math>c_i</math> होती है। जो संख्या <math>x_i</math> इंगित करता है कि <math>i</math> प्रकार की कितनी वस्तुएं हैं जो हम ख़रीदते हैं। यदि व्यवरोध <math>A\mathbf{x}\geq \mathbf{b}</math> संतुष्ट हैं, तो यह कहा जाता है कि <math>\mathbf{x}</math> एक | '''अंतर्ज्ञान''': मान लीजिए <math>n</math> प्रकार की वस्तु है और प्रत्येक प्रकार की वस्तु <math>i</math> की संबद्ध कीमत <math>c_i</math> होती है। जो संख्या <math>x_i</math> इंगित करता है कि <math>i</math> प्रकार की कितनी वस्तुएं हैं जो हम ख़रीदते हैं। यदि व्यवरोध <math>A\mathbf{x}\geq \mathbf{b}</math> संतुष्ट हैं, तो यह कहा जाता है कि <math>\mathbf{x}</math> एक आच्छादन है आच्छादित संरचनाएं मिश्रित संदर्भ पर निर्भर करती हैं। अंत में, उपरोक्त पूर्णांक रैखिक प्रोग्राम का इष्टतम समाधान न्यूनतम मूल्य को आच्छादित करता है। | ||
==समस्याओं को आच्छादित करने के प्रकार== | ==समस्याओं को आच्छादित करने के प्रकार== | ||
[[ ग्राफ सिद्धांत |ग्राफ सिद्धांत]], [[ कम्प्यूटेशनल ज्यामिति |कम्प्यूटेशनल ज्यामिति]] में विभिन्न प्रकार की | [[ ग्राफ सिद्धांत |ग्राफ सिद्धांत]], [[ कम्प्यूटेशनल ज्यामिति |कम्प्यूटेशनल ज्यामिति]] में विभिन्न प्रकार की आच्छादन समस्याएं हैं; और अधिक श्रेणी आच्छादन समस्याएं देखें।। समस्या के अन्य प्रसंभाव्यता संबंधित संस्करण मिल सकते हैं। <ref>{{cite web|author = Douek-Pinkovich, Y., Ben-Gal, I., & Raviv, T. (2022)|title = The Stochastic Test Collection Problem: Models, Exact and Heuristic Solution Approaches |url = http://www.eng.tau.ac.il/~bengal/STCP.pdf|publisher = European Journal of Operational Research, 299 (2022), 945–959} }}</ref> | ||
उदाहरण के लिए [[पेट्री नेट|पेट्री]] मूल्य के लिए, | उदाहरण के लिए [[पेट्री नेट|पेट्री]] मूल्य के लिए, आच्छादन समस्या को प्रश्न के रूप में परिभाषित किया गया है यदि किसी दिए गए अंकन, मूल्य का एक क्रम सम्मिलित है, जैसे कि कुछ बृहत् (या बराबर) अंकन तक पहुंचा जा सकता है। यहां बृहत का तात्पर्य है कि सभी घटक कम से कम दिए गए अंकन के जितने बड़े हैं और कम से कम एक उपयुक्त रूप से बड़ा है। | ||
== इंद्रधनुष का आच्छादित और अंतर्द्वंदव (कॉन्फ्लिक्ट)-मुक्त आच्छादित == | == इंद्रधनुष का आच्छादित और अंतर्द्वंदव (कॉन्फ्लिक्ट)-मुक्त आच्छादित == | ||
कुछ | कुछ आच्छादन समस्याओं में, आच्छादन को कुछ अतिरिक्त आवश्यकताओं को पूरा करना चाहिए। विशेष रूप से, इंद्रधनुष आच्छादन समस्या में, प्रत्येक मूल वस्तु का एक रंग होता है, और यह आवश्यक है कि आच्छादन में प्रत्येक रंग की एक (या अधिक से अधिक एक) वस्तु सम्मिलित हो। इंद्रधनुष आच्छादन का अध्ययन किया गया था उदाहरण [[अंतराल (गणित)]] द्वारा बिंदुओं को आच्छादित करने के लिए:<ref>{{Cite journal|last1=Arkin|first1=Esther M.|last2=Banik|first2=Aritra|last3=Carmi|first3=Paz|last4=Citovsky|first4=Gui|last5=Katz|first5=Matthew J.|last6=Mitchell|first6=Joseph S. B.|last7=Simakov|first7=Marina|date=2018-12-11|title=रंगीन बिंदुओं का चयन करना और उन्हें ढंकना|journal=Discrete Applied Mathematics|language=en|volume=250|pages=75–86|doi=10.1016/j.dam.2018.05.011|issn=0166-218X|doi-access=free}}</ref> | ||
* [[वास्तविक रेखा]] पर n रंगीन अंतरालों का एक समुच्चय J है, और वास्तविक रेखा पर बिंदुओं का एक समुच्चय है। | * [[वास्तविक रेखा]] पर n रंगीन अंतरालों का एक समुच्चय J है, और वास्तविक रेखा पर बिंदुओं का एक समुच्चय है। | ||
* J के एक उपसमुच्चय Q को इंद्रधनुषी समुच्चय कहा जाता है यदि इसमें प्रत्येक रंग का अधिक से अधिक एक अंतराल हो। | * J के एक उपसमुच्चय Q को इंद्रधनुषी समुच्चय कहा जाता है यदि इसमें प्रत्येक रंग का अधिक से अधिक एक अंतराल हो। | ||
* अंतराल J के एक [[सबसेट|उप-समुच्चय]] को P का | * अंतराल J के एक [[सबसेट|उप-समुच्चय]] को P का आच्छादन कहा जाता है यदि P का प्रत्येक बिंदु Q के कम से कम एक अंतराल में समाहित है। | ||
* इंद्रधनुष | * इंद्रधनुष आच्छादन समस्या इंद्रधनुष समुच्चय Q को खोजने की समस्या है जो कि P का आच्छादन है। | ||
समस्या एनपी-कठिन (रैखिक एसएटी से कमी से) है। | समस्या एनपी-कठिन (रैखिक एसएटी से कमी से) है। | ||
अधिक सामान्य धारणा ' अंतर्द्वंदव-मुक्त | अधिक सामान्य धारणा ' अंतर्द्वंदव-मुक्त आच्छादन' है।<ref>{{Cite journal|last1=Banik|first1=Aritra|last2=Sahlot|first2=Vibha|last3=Saurabh|first3=Saket|date=2020-08-01|title=ज्यामितीय संघर्ष मुक्त कवरिंग समस्याओं के लिए सन्निकटन एल्गोरिदम|url=http://www.sciencedirect.com/science/article/pii/S0925772119301324|journal=Computational Geometry|language=en|volume=89|pages=101591|doi=10.1016/j.comgeo.2019.101591|s2cid=209959954 |issn=0925-7721}}</ref> इस समस्या में: | ||
* m वस्तु का एक समुच्चय O है, और O पर एक अंतर्द्वंदव -आरेख ''G<sub>O</sub>'' है। | * m वस्तु का एक समुच्चय O है, और O पर एक अंतर्द्वंदव -आरेख ''G<sub>O</sub>'' है। | ||
| Line 43: | Line 43: | ||
* एक इंद्रधनुष समुच्चय विशेष स्थितियों में एक ''अंतर्द्वंदव''-मुक्त समुच्चय है जिसमें G<sub>O</sub>अलग-अलग समूहों से बना है, जहां प्रत्येक समूह एक रंग का प्रतिनिधित्व करता है। | * एक इंद्रधनुष समुच्चय विशेष स्थितियों में एक ''अंतर्द्वंदव''-मुक्त समुच्चय है जिसमें G<sub>O</sub>अलग-अलग समूहों से बना है, जहां प्रत्येक समूह एक रंग का प्रतिनिधित्व करता है। | ||
अंतर्द्वंदव-मुक्त समुच्चय | अंतर्द्वंदव-मुक्त समुच्चय आच्छादन O का एक अंतर्द्वंदव-मुक्त उपसमुच्चय खोजने की समस्या है जो कि P. बनिक, पानोलन, रमन, सहलोत और सौरभ का एक आच्छादन है<ref>{{Cite journal|last1=Banik|first1=Aritra|last2=Panolan|first2=Fahad|last3=Raman|first3=Venkatesh|last4=Sahlot|first4=Vibha|last5=Saurabh|first5=Saket|date=2020-01-01|title=विरोधाभासी होने वाली ज्यामितीय आवरण समस्याओं की पैरामिट्रीकृत जटिलता|url=https://doi.org/10.1007/s00453-019-00600-w|journal=Algorithmica|language=en|volume=82|issue=1|pages=1–19|doi=10.1007/s00453-019-00600-w|s2cid=254027914 |issn=1432-0541}}</ref> गणितीय प्रमाण निम्नलिखित विशेष स्थितियों के लिए जिसमें अंतर्द्वंदव-आरेख ने [[वृक्षारोपण|अरबोरिसिटी]] को सीमित किया है: | ||
* यदि ज्यामितीय आच्छादित समस्या निश्चित-पैरामीटर आसानी से प्रभावित होने वाला (एफपीटी) होता है, तो अंतर्द्वंदव-मुक्त ज्यामितीय आच्छादित समस्या एफपीटी है। | * यदि ज्यामितीय आच्छादित समस्या निश्चित-पैरामीटर आसानी से प्रभावित होने वाला (एफपीटी) होता है, तो अंतर्द्वंदव-मुक्त ज्यामितीय आच्छादित समस्या एफपीटी है। | ||
Revision as of 08:00, 16 May 2023
साहचर्य और कंप्यूटर विज्ञान में, समस्याओं को आच्छादित करना कम्प्यूटेशनल समस्याएं हैं जो पूछती हैं कि क्या एक निश्चित सांयोगिक संरचना दूसरे को 'आच्छादित' करता है, या ऐसा करने के लिए संरचना कितनी बड़ी होनी चाहिए। आच्छादन समस्याएं न्यूनीकरण (गणित) की समस्याएँ हैं और सामान्य रूप से पूर्णांक रैखिक प्रोग्राम हैं, जिनकी दोहरी समस्याओं को पैकिंग समस्याएं कहा जाता है।
आच्छादन (कवरिंग) समस्याओं का सबसे प्रमुख उदाहरण समुच्चय आच्छादित समस्या है, जो अघाती समुच्चय समस्या के बराबर है, और इसके विशेष स्थिति मे, शीर्ष आच्छादित समस्या और कोर आच्छादित समस्या है।
सामान्य रैखिक प्रोग्रामिंग सूत्रीकरण
रैखिक प्रोग्रामिंग के संदर्भ में, किसी भी रैखिक प्रोग्राम को एक आच्छादन समस्या के रूप में विचार कर सकते हैं यदि प्रतिबंध आव्यूह (गणित), उद्देश्य फलन, और दक्षिणावर्ती पक्ष की ओर गुणांक गैर-ऋणात्मक हैं।[1] अधिक परिशुद्ध रूप से, निम्नलिखित सामान्य पूर्णांक रैखिक प्रोग्राम पर विचार करें:
| न्यूनतम | |
| यदि | |
| . |
इस तरह के एक पूर्णांक रैखिक प्रोग्राम को आच्छादन समस्या कहा जाता है यदि सभी के लिए और .
अंतर्ज्ञान: मान लीजिए प्रकार की वस्तु है और प्रत्येक प्रकार की वस्तु की संबद्ध कीमत होती है। जो संख्या इंगित करता है कि प्रकार की कितनी वस्तुएं हैं जो हम ख़रीदते हैं। यदि व्यवरोध संतुष्ट हैं, तो यह कहा जाता है कि एक आच्छादन है आच्छादित संरचनाएं मिश्रित संदर्भ पर निर्भर करती हैं। अंत में, उपरोक्त पूर्णांक रैखिक प्रोग्राम का इष्टतम समाधान न्यूनतम मूल्य को आच्छादित करता है।
समस्याओं को आच्छादित करने के प्रकार
ग्राफ सिद्धांत, कम्प्यूटेशनल ज्यामिति में विभिन्न प्रकार की आच्छादन समस्याएं हैं; और अधिक श्रेणी आच्छादन समस्याएं देखें।। समस्या के अन्य प्रसंभाव्यता संबंधित संस्करण मिल सकते हैं। [2]
उदाहरण के लिए पेट्री मूल्य के लिए, आच्छादन समस्या को प्रश्न के रूप में परिभाषित किया गया है यदि किसी दिए गए अंकन, मूल्य का एक क्रम सम्मिलित है, जैसे कि कुछ बृहत् (या बराबर) अंकन तक पहुंचा जा सकता है। यहां बृहत का तात्पर्य है कि सभी घटक कम से कम दिए गए अंकन के जितने बड़े हैं और कम से कम एक उपयुक्त रूप से बड़ा है।
इंद्रधनुष का आच्छादित और अंतर्द्वंदव (कॉन्फ्लिक्ट)-मुक्त आच्छादित
कुछ आच्छादन समस्याओं में, आच्छादन को कुछ अतिरिक्त आवश्यकताओं को पूरा करना चाहिए। विशेष रूप से, इंद्रधनुष आच्छादन समस्या में, प्रत्येक मूल वस्तु का एक रंग होता है, और यह आवश्यक है कि आच्छादन में प्रत्येक रंग की एक (या अधिक से अधिक एक) वस्तु सम्मिलित हो। इंद्रधनुष आच्छादन का अध्ययन किया गया था उदाहरण अंतराल (गणित) द्वारा बिंदुओं को आच्छादित करने के लिए:[3]
- वास्तविक रेखा पर n रंगीन अंतरालों का एक समुच्चय J है, और वास्तविक रेखा पर बिंदुओं का एक समुच्चय है।
- J के एक उपसमुच्चय Q को इंद्रधनुषी समुच्चय कहा जाता है यदि इसमें प्रत्येक रंग का अधिक से अधिक एक अंतराल हो।
- अंतराल J के एक उप-समुच्चय को P का आच्छादन कहा जाता है यदि P का प्रत्येक बिंदु Q के कम से कम एक अंतराल में समाहित है।
- इंद्रधनुष आच्छादन समस्या इंद्रधनुष समुच्चय Q को खोजने की समस्या है जो कि P का आच्छादन है।
समस्या एनपी-कठिन (रैखिक एसएटी से कमी से) है।
अधिक सामान्य धारणा ' अंतर्द्वंदव-मुक्त आच्छादन' है।[4] इस समस्या में:
- m वस्तु का एक समुच्चय O है, और O पर एक अंतर्द्वंदव -आरेख GO है।
- O के एक उपसमुच्चय Q को अंतर्द्वंदव-मुक्त कहा जाता है यदि यह GO में एक स्वतंत्र समुच्चय है, अर्थात, Q में कोई भी दो वस्तुएँ GO में एक कोर से जुड़ी नहीं हैं।
- एक इंद्रधनुष समुच्चय विशेष स्थितियों में एक अंतर्द्वंदव-मुक्त समुच्चय है जिसमें GOअलग-अलग समूहों से बना है, जहां प्रत्येक समूह एक रंग का प्रतिनिधित्व करता है।
अंतर्द्वंदव-मुक्त समुच्चय आच्छादन O का एक अंतर्द्वंदव-मुक्त उपसमुच्चय खोजने की समस्या है जो कि P. बनिक, पानोलन, रमन, सहलोत और सौरभ का एक आच्छादन है[5] गणितीय प्रमाण निम्नलिखित विशेष स्थितियों के लिए जिसमें अंतर्द्वंदव-आरेख ने अरबोरिसिटी को सीमित किया है:
- यदि ज्यामितीय आच्छादित समस्या निश्चित-पैरामीटर आसानी से प्रभावित होने वाला (एफपीटी) होता है, तो अंतर्द्वंदव-मुक्त ज्यामितीय आच्छादित समस्या एफपीटी है।
- यदि ज्यामितीय आच्छादित समस्या एक r-सन्निकटन एल्गोरिथ्म को स्वीकार करती है, तो अंतर्द्वंदव-मुक्त ज्यामितीय आच्छादित समस्या एफपीटी समय में समान सन्निकटन एल्गोरिथ्म को स्वीकार करती है।
संदर्भ
- ↑ Vazirani, Vijay V. (2001). सन्निकटन एल्गोरिदम. Springer-Verlag. ISBN 3-540-65367-8.: 112
- ↑ Douek-Pinkovich, Y., Ben-Gal, I., & Raviv, T. (2022). "The Stochastic Test Collection Problem: Models, Exact and Heuristic Solution Approaches" (PDF). European Journal of Operational Research, 299 (2022), 945–959}.
{{cite web}}: CS1 maint: multiple names: authors list (link) - ↑ Arkin, Esther M.; Banik, Aritra; Carmi, Paz; Citovsky, Gui; Katz, Matthew J.; Mitchell, Joseph S. B.; Simakov, Marina (2018-12-11). "रंगीन बिंदुओं का चयन करना और उन्हें ढंकना". Discrete Applied Mathematics (in English). 250: 75–86. doi:10.1016/j.dam.2018.05.011. ISSN 0166-218X.
- ↑ Banik, Aritra; Sahlot, Vibha; Saurabh, Saket (2020-08-01). "ज्यामितीय संघर्ष मुक्त कवरिंग समस्याओं के लिए सन्निकटन एल्गोरिदम". Computational Geometry (in English). 89: 101591. doi:10.1016/j.comgeo.2019.101591. ISSN 0925-7721. S2CID 209959954.
- ↑ Banik, Aritra; Panolan, Fahad; Raman, Venkatesh; Sahlot, Vibha; Saurabh, Saket (2020-01-01). "विरोधाभासी होने वाली ज्यामितीय आवरण समस्याओं की पैरामिट्रीकृत जटिलता". Algorithmica (in English). 82 (1): 1–19. doi:10.1007/s00453-019-00600-w. ISSN 1432-0541. S2CID 254027914.
