बाधा संतुष्टि की समस्या

Not to be confused with Communicating sequential processes.

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

समस्याओं के उदाहरण जिन्हें एक बाधा संतुष्टि समस्या के रूप में प्रतिरूपित किया जा सकता है उनमें शामिल हैं:

• अनुमान टाइप करें
• आठ रानियों की पहेली
• ग्राफ रंगना
• अधिकतम कटौती
• सुडोकू, क्रॉसवर्ड, फूटोशिकी, तंबाकू से होने वाली बीमारी (क्रॉस सम्स), न्यूम्ब्रिक्स, हिडाटो और कई अन्य तर्क पहेली

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

औपचारिक परिभाषा

औपचारिक रूप से, एक बाधा संतुष्टि समस्या को ट्रिपल के रूप में परिभाषित किया गया है $\langle X,D,C\rangle$, कहाँ

• $X=\{X_{1},\ldots ,X_{n}\}$ चर का एक सेट है,
• $D=\{D_{1},\ldots ,D_{n}\}$ मूल्यों के उनके संबंधित डोमेन का एक सेट है, और
• $C=\{C_{1},\ldots ,C_{m}\}$ बाधाओं का एक समूह है।

प्रत्येक चर $X_{i}$ गैर-खाली डोमेन में मान ले सकता है $D_{i}$. हर विवशता $C_{j}\in C$ बदले में एक जोड़ी है $\langle t_{j},R_{j}\rangle$, कहाँ $t_{j}\subset X$ का उपसमुच्चय है $k$ चर और $R_{j}$ एक है $k$डोमेन के संबंधित उपसमुच्चय पर -अरी संबंध (गणित)। $D_{j}$. वेरिएबल्स का मूल्यांकन डोमेन के संबंधित सबसेट में वेरिएबल्स के एक सबसेट से मूल्यों के एक विशेष सेट के लिए एक फ़ंक्शन है। एक विकास $v$ एक बाधा को संतुष्ट करता है $\langle t_{j},R_{j}\rangle$ यदि मान चर को सौंपा गया है $t_{j}$ संबंध को संतुष्ट करता है $R_{j}$.

एक मूल्यांकन सुसंगत है यदि यह किसी भी बाधा का उल्लंघन नहीं करता है। एक मूल्यांकन पूर्ण होता है यदि इसमें सभी चर शामिल होते हैं। एक मूल्यांकन एक समाधान है यदि यह सुसंगत और पूर्ण है; इस तरह के मूल्यांकन को बाधा संतुष्टि समस्या को हल करने के लिए कहा जाता है।

समाधान

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

बाधा प्रसार तकनीक एक बाधा संतुष्टि समस्या को संशोधित करने के लिए उपयोग की जाने वाली विधियाँ हैं। अधिक सटीक रूप से, वे ऐसे तरीके हैं जो स्थानीय स्थिरता के एक रूप को लागू करते हैं, जो चर और/या बाधाओं के समूह की स्थिरता से संबंधित शर्तें हैं। बाधा प्रसार के विभिन्न उपयोग हैं। सबसे पहले, यह एक समस्या को समतुल्य में बदल देता है लेकिन आमतौर पर हल करना आसान होता है। दूसरा, यह समस्याओं की संतुष्टि या असंतोषजनक साबित हो सकता है। यह सामान्य रूप से होने की गारंटी नहीं है; हालाँकि, यह हमेशा कुछ प्रकार की बाधा प्रसार और/या कुछ प्रकार की समस्याओं के लिए होता है। स्थानीय संगति के सर्वाधिक ज्ञात और उपयोग किए जाने वाले रूप चाप संगति, हाइपर-आर्क संगति और पथ संगति हैं। सबसे लोकप्रिय बाधा प्रचार विधि एसी एसी-3 एल्गोरिथम है, जो आर्क स्थिरता को लागू करती है।

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

सैद्धांतिक पहलू

निर्णय समस्याएं

सीएसपी का अध्ययन कम्प्यूटेशनल जटिलता सिद्धांत और परिमित मॉडल सिद्धांत में भी किया जाता है। एक महत्वपूर्ण प्रश्न यह है कि क्या संबंधों के प्रत्येक सेट के लिए, सभी सीएसपी का सेट जिसे केवल उस सेट से चुने गए संबंधों का उपयोग करके दर्शाया जा सकता है, या तो पी (जटिलता) या एनपी-पूर्ण में है। यदि ऐसा द्विभाजन प्रमेय सत्य है, तो सीएसपी एनपी (जटिलता) के सबसे बड़े ज्ञात उपसमुच्चयों में से एक प्रदान करते हैं जो एनपी-मध्यवर्ती समस्याओं से बचा जाता है, जिसका अस्तित्व लेडनर के प्रमेय द्वारा इस धारणा के तहत प्रदर्शित किया गया था कि पी बनाम एनपी समस्या|पी ≠ एनपी। शेफर का द्विभाजन प्रमेय उस मामले को संभालता है जब सभी उपलब्ध संबंध बूलियन ऑपरेटर (बूलियन बीजगणित) होते हैं, जो कि डोमेन आकार 2 के लिए होता है। शेफर के द्विभाजन प्रमेय को हाल ही में संबंधों के एक बड़े वर्ग के लिए सामान्यीकृत किया गया था। सीएसपी के अधिकांश वर्ग जिन्हें ट्रैक्टेबल के रूप में जाना जाता है, वे हैं जहां बाधाओं के hypergraph ने पेड़ की चौड़ाई को सीमित कर दिया है (और बाधा संबंधों के सेट पर कोई प्रतिबंध नहीं है), या जहां बाधाओं का मनमाना रूप है, लेकिन अनिवार्य रूप से गैर-एकात्मक बहुरूपता मौजूद हैं बाधा संबंधों के सेट का।

प्रत्येक सीएसपी को संयोजन क्वेरी रोकथाम समस्या के रूप में भी माना जा सकता है।

कार्य समस्याएं

इसी तरह की स्थिति कार्यात्मक वर्गों एफपी (जटिलता) और तीव्र-पी | # पी के बीच मौजूद है। लेडनर के प्रमेय के सामान्यीकरण से, न तो FP और न ही Sharp-P-पूर्ण|#P-पूर्ण जब तक FP ≠ #P है, तब तक समस्याएँ हैं। जैसा कि निर्णय मामले में, #CSP में एक समस्या संबंधों के एक समूह द्वारा परिभाषित की जाती है। प्रत्येक समस्या एक बूलियन तर्क सूत्र को इनपुट के रूप में लेती है और कार्य संतोषजनक असाइनमेंट की संख्या की गणना करना है। इसे बड़े डोमेन आकार का उपयोग करके और प्रत्येक संतोषजनक असाइनमेंट के लिए एक भार जोड़कर और इन भारों के योग की गणना करके इसे और सामान्यीकृत किया जा सकता है। यह ज्ञात है कि कोई भी जटिल भारित #सीएसपी समस्या या तो एफपी या #पी-हार्ड में है।

वेरिएंट

बाधा संतुष्टि समस्या का क्लासिक मॉडल स्थिर, अनम्य बाधाओं के मॉडल को परिभाषित करता है। यह कठोर मॉडल एक कमी है जिससे समस्याओं को आसानी से प्रस्तुत करना कठिन हो जाता है। मॉडल को विभिन्न प्रकार की समस्याओं के अनुकूल बनाने के लिए बुनियादी सीएसपी परिभाषा के कई संशोधन प्रस्तावित किए गए हैं।

गतिशील सीएसपी

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

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

लचीला सीएसपी

क्लासिक सीएसपी बाधाओं को कठिन मानते हैं, जिसका अर्थ है कि वे अनिवार्य हैं (प्रत्येक समाधान को उन सभी को संतुष्ट करना चाहिए) और अनम्य (इस अर्थ में कि उन्हें पूरी तरह से संतुष्ट होना चाहिए या फिर उनका पूरी तरह से उल्लंघन किया जाना चाहिए)। 'लचीला सीएसपी उन धारणाओं को आराम देता है, आंशिक रूप से बाधाओं को आराम देता है और समाधान को उन सभी का पालन नहीं करने देता है। यह वरीयता-आधारित योजना में प्राथमिकताओं के समान है। कुछ प्रकार के लचीले सीएसपी में शामिल हैं:

• मैक्स-सीएसपी, जहां कई बाधाओं का उल्लंघन करने की अनुमति है, और समाधान की गुणवत्ता को संतुष्ट बाधाओं की संख्या से मापा जाता है।
• भारित बाधा संतुष्टि समस्या, एक MAX-CSP जिसमें एक बाधा के प्रत्येक उल्लंघन को पूर्वनिर्धारित वरीयता के अनुसार भारित किया जाता है। इस प्रकार अधिक वजन के साथ संतोषजनक बाधा को प्राथमिकता दी जाती है।
• फजी सीएसपी मॉडल बाधा फजी लॉजिक संबंधों के रूप में होती है जिसमें एक बाधा की संतुष्टि इसके चर के मूल्यों का एक निरंतर कार्य है, पूरी तरह से उल्लंघन करने के लिए पूरी तरह से संतुष्ट से जा रहा है।

विकेंद्रीकृत सीएसपी

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

यह भी देखें

• बाधा समग्र ग्राफ
• बाधा प्रोग्रामिंग
• घोषणात्मक प्रोग्रामिंग
• विवश अनुकूलन (COP)
• वितरित बाधा अनुकूलन
• ग्राफ समरूपता
• अनोखा खेल अनुमान
• भारित बाधा संतुष्टि समस्या (WCSP)

अग्रिम पठन

• A quick introduction to constraint satisfaction on YouTube
• Steven Minton; Andy Philips; Mark D. Johnston; Philip Laird (1993). "Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems". Journal of Artificial Intelligence Research. 58 (1–3): 161–205. CiteSeerX 10.1.1.308.6637. doi:10.1016/0004-3702(92)90007-k. S2CID 14830518.
• Tsang, Edward (1993). Foundations of Constraint Satisfaction. Academic Press. ISBN 0-12-701610-4
• Chen, Hubie (December 2009). "A Rendezvous of Logic, Complexity, and Algebra". ACM Computing Surveys. 42 (1): 1–32. arXiv:cs/0611018. doi:10.1145/1592451.1592453. S2CID 11975818.
• Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 1-55860-890-7
• Apt, Krzysztof (2003). Principles of constraint programming. Cambridge University Press. ISBN 9780521825832. ISBN 0-521-82583-0
• Lecoutre, Christophe (2009). Constraint Networks: Techniques and Algorithms. ISTE/Wiley. ISBN 978-1-84821-106-3
• Tomás Feder, Constraint satisfaction: a personal perspective, manuscript.
• Constraints archive
• Forced Satisfiable CSP Benchmarks of Model RB
• Benchmarks – XML representation of CSP instances
• XCSP3 – An XML-based format designed to represent CSP instances
• Constraint Propagation – Dissertation by Guido Tack giving a good survey of theory and implementation issues