बाधा संतुष्टि की समस्या: Difference between revisions

Revision as of 11:01, 7 March 2023

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

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

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

इन्हें अधिकांशतः बाधा प्रोग्रामिंग, एएसपी, बूलियन एसएटी और एसएमटी सॉल्वर के ट्यूटोरियल के साथ प्रदान किया जाता है। सामान्य स्थितियों में, बाधा की समस्याएं बहुत कठिन हो सकती हैं, और इनमें से कुछ सरल प्रणालियों में अभिव्यक्त नहीं हो सकती हैं। वास्तविक जीवन के उदाहरणों में स्वचालित योजना,^[6]^[7] शाब्दिक असंबद्धता,^[8]^[9] संगीतशास्त्र,^[10] कॉन्फ़िगर करें, मूल्य और उद्धरण^[11] और संसाधन आवंटन सम्मिलित है।^[12]

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

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

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

$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}$ .

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

समाधान

परिमित डोमेन पर बाधा संतुष्टि समस्याओं को आम तौर पर खोज एल्गोरिद्म के एक रूप का उपयोग करके हल किया जाता है। सबसे अधिक उपयोग की जाने वाली तकनीकें बैक ट्रैकिंग , बाधा प्रसार और स्थानीय खोज (अनुकूलन) के प्रकार हैं। इन तकनीकों को भी अधिकांशतः संयुक्त किया जाता है, जैसा कि बहुत बड़े पैमाने पर पड़ोस की खोज पद्धति में होता है, और वर्तमान शोध में अन्य प्रौद्योगिकियां सम्मिलित होती हैं जैसे रैखिक प्रोग्रामिंग।^[14]

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

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

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

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

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

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

सीएसपी के अधिकांश वर्ग जिन्हें ट्रैक्टेबल के रूप में जाना जाता है, वे हैं जहां बाधाओं के hypergraph ने पेड़ की चौड़ाई को सीमित कर दिया है (और बाधा संबंधों के सेट पर कोई प्रतिबंध नहीं है), या जहां बाधाओं का मनमाना रूप है, लेकिन अनिवार्य रूप से गैर-एकात्मक बहुरूपता मौजूद हैं^{[clarification needed]} बाधा संबंधों के सेट का।

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

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

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

वेरिएंट

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

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

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

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

लचीला सीएसपी

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

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

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

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

यह भी देखें

संदर्भ

↑ Lecoutre, Christophe (2013). Constraint Networks: Techniques and Algorithms. Wiley. p. 26. ISBN 978-1-118-61791-5.
↑ "Constraints – incl. option to publish open access". springer.com (in English). Retrieved 2019-10-03.
↑ Chandra, Satish, et al. "Type inference for static compilation of JavaScript." ACM SIGPLAN Notices 51.10 (2016): 410-429.
↑ Jim, Trevor, and Jens Palsberg. "Type inference in systems of recursive types with subtyping." Available on authors’ web page (1999).
↑ Farhi, Edward and Harrow, Aram. "Quantum Supremacy through the Quantum Approximate Optimization Algorithm." arXiv:1602.07674
↑ Malik Ghallab; Dana Nau; Paolo Traverso (21 May 2004). Automated Planning: Theory and Practice. Elsevier. pp. 1–. ISBN 978-0-08-049051-9.
↑ Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning, Archived 2009-02-06 at the Wayback Machine Ian Miguel – slides.
↑ Demetriou, George C. "Lexical disambiguation using constraint handling in Prolog (CHIP)." Proceedings of the sixth conference on European chapter of the Association for Computational Linguistics. Association for Computational Linguistics, 1993.
↑ MacDonald, Maryellen C., and Mark S. Seidenberg. "Constraint satisfaction accounts of lexical and sentence comprehension." Handbook of Psycholinguistics (Second Edition). 2006. 581–611.
↑ Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. "GELISP: A FRAMEWORK TO REPRESENT MUSICAL CONSTRAINT SATISFACTION PROBLEMS AND SEARCH STRATEGIES." Journal of Theoretical and Applied Information Technology 86 (2). 2016. 327–331.
↑ Applying constraint satisfaction approach to solve product configuration problems with cardinality-based configuration rules, Dong Yang & Ming Dong, Journal of Intelligent Manufacturing volume 24, pages99–111 (2013)
↑ Modi, Pragnesh Jay, et al. "A dynamic distributed constraint satisfaction approach to resource allocation." International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg, 2001.
↑ Stuart Jonathan Russell; Peter Norvig (2010). Artificial Intelligence: A Modern Approach. Prentice Hall. p. Chapter 6. ISBN 9780136042594.
↑ Hybrid optimization : the ten years of CPAIOR. Milano, Michela., Van Hentenryck, Pascal., International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems. New York: Springer. 2011. ISBN 9781441916440. OCLC 695387020.{{cite book}}: CS1 maint: others (link)
↑ Bodirsky, Manuel; Pinsker, Michael (2011). "Schaefer's theorem for graphs". Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC '11). Association for Computing Machinery. pp. 655–664. arXiv:1011.2894. Bibcode:2010arXiv1011.2894B. doi:10.1145/1993636.1993724. ISBN 978-1-4503-0691-1. S2CID 47097319.
↑ Kolaitis, Phokion G.; Vardi, Moshe Y. (2000). "संयोजन-प्रश्न नियंत्रण और बाधा संतुष्टि". Journal of Computer and System Sciences. 61 (2): 302–332. doi:10.1006/jcss.2000.1713.
↑ Cai, Jin-Yi; Chen, Xi (2012). "जटिल भार के साथ सीएसपी की गिनती की जटिलता". Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12). pp. 909–920. arXiv:1111.2384. doi:10.1145/2213977.2214059. ISBN 978-1-4503-1245-5. S2CID 53245129.
↑ Miguel, Ian (July 2001). Dynamic Flexible Constraint Satisfaction and its Application to AI Planning (Ph.D. thesis). University of Edinburgh School of Informatics. CiteSeerX 10.1.1.9.6733. hdl:1842/326.
↑ Dechter, R. and Dechter, A., Belief Maintenance in Dynamic Constraint Networks Archived 2012-11-17 at the Wayback Machine In Proc. of AAAI-88, 37–42.
↑ Solution reuse in dynamic constraint satisfaction problems, Thomas Schiex
↑ Duffy, K.R.; Leith, D.J. (August 2013), "Decentralized Constraint Satisfaction", IEEE/ACM Transactions on Networking, 21(4), vol. 21, pp. 1298–1308, arXiv:1103.3240, doi:10.1109/TNET.2012.2222923, S2CID 11504393

अग्रिम पठन

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

[1] Lecoutre, Christophe (2013). Constraint Networks: Techniques and Algorithms. Wiley. p. 26. ISBN 978-1-118-61791-5.

[2] "Constraints – incl. option to publish open access". springer.com (in English). Retrieved 2019-10-03.

[3] Chandra, Satish, et al. "Type inference for static compilation of JavaScript." ACM SIGPLAN Notices 51.10 (2016): 410-429.

[4] Jim, Trevor, and Jens Palsberg. "Type inference in systems of recursive types with subtyping." Available on authors’ web page (1999).

[5] Farhi, Edward and Harrow, Aram. "Quantum Supremacy through the Quantum Approximate Optimization Algorithm." arXiv:1602.07674

[GhallabNau2004-6] Malik Ghallab; Dana Nau; Paolo Traverso (21 May 2004). Automated Planning: Theory and Practice. Elsevier. pp. 1–. ISBN 978-0-08-049051-9.

[7] Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning, Archived 2009-02-06 at the Wayback Machine Ian Miguel – slides.

[8] Demetriou, George C. "Lexical disambiguation using constraint handling in Prolog (CHIP)." Proceedings of the sixth conference on European chapter of the Association for Computational Linguistics. Association for Computational Linguistics, 1993.

[9] MacDonald, Maryellen C., and Mark S. Seidenberg. "Constraint satisfaction accounts of lexical and sentence comprehension." Handbook of Psycholinguistics (Second Edition). 2006. 581–611.

[10] Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. "GELISP: A FRAMEWORK TO REPRESENT MUSICAL CONSTRAINT SATISFACTION PROBLEMS AND SEARCH STRATEGIES." Journal of Theoretical and Applied Information Technology 86 (2). 2016. 327–331.

[11] Applying constraint satisfaction approach to solve product configuration problems with cardinality-based configuration rules, Dong Yang & Ming Dong, Journal of Intelligent Manufacturing volume 24, pages99–111 (2013)

[12] Modi, Pragnesh Jay, et al. "A dynamic distributed constraint satisfaction approach to resource allocation." International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg, 2001.

[Russell2010-13] Stuart Jonathan Russell; Peter Norvig (2010). Artificial Intelligence: A Modern Approach. Prentice Hall. p. Chapter 6. ISBN 9780136042594.

[14] Hybrid optimization : the ten years of CPAIOR. Milano, Michela., Van Hentenryck, Pascal., International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems. New York: Springer. 2011. ISBN 9781441916440. OCLC 695387020.{{cite book}}: CS1 maint: others (link)

[15] Bodirsky, Manuel; Pinsker, Michael (2011). "Schaefer's theorem for graphs". Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC '11). Association for Computing Machinery. pp. 655–664. arXiv:1011.2894. Bibcode:2010arXiv1011.2894B. doi:10.1145/1993636.1993724. ISBN 978-1-4503-0691-1. S2CID 47097319.

[16] Kolaitis, Phokion G.; Vardi, Moshe Y. (2000). "संयोजन-प्रश्न नियंत्रण और बाधा संतुष्टि". Journal of Computer and System Sciences. 61 (2): 302–332. doi:10.1006/jcss.2000.1713.

[17] Cai, Jin-Yi; Chen, Xi (2012). "जटिल भार के साथ सीएसपी की गिनती की जटिलता". Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12). pp. 909–920. arXiv:1111.2384. doi:10.1145/2213977.2214059. ISBN 978-1-4503-1245-5. S2CID 53245129.

[18] Miguel, Ian (July 2001). Dynamic Flexible Constraint Satisfaction and its Application to AI Planning (Ph.D. thesis). University of Edinburgh School of Informatics. CiteSeerX 10.1.1.9.6733. hdl:1842/326.

[19] Dechter, R. and Dechter, A., Belief Maintenance in Dynamic Constraint Networks Archived 2012-11-17 at the Wayback Machine In Proc. of AAAI-88, 37–42.

[20] Solution reuse in dynamic constraint satisfaction problems, Thomas Schiex

[cfl-21] Duffy, K.R.; Leith, D.J. (August 2013), "Decentralized Constraint Satisfaction", IEEE/ACM Transactions on Networking, 21(4), vol. 21, pp. 1298–1308, arXiv:1103.3240, doi:10.1109/TNET.2012.2222923, S2CID 11504393

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

@@ Line 1: / Line 1: @@
 {{distinguish|Communicating sequential processes}}
 {{more citations needed|date=November 2014}}
-बाधा संतुष्टि समस्याएं (सीएसपी) गणितीय प्रश्न हैं जिन्हें वस्तुओं के एक सेट के रूप में परिभाषित किया गया है जिनके [[राज्य (कंप्यूटर विज्ञान)]] को कई बाधाओं (गणित) या [[सीमा (गणित)]] को पूरा करना चाहिए। सीएसपी परिमित बाधाओं के एक सजातीय संग्रह के रूप में एक समस्या में संस्थाओं का प्रतिनिधित्व करते हैं, जो कि बाधा संतुष्टि विधियों द्वारा हल किया जाता है। सीएसपी [[ कृत्रिम होशियारी ]] और [[गतिविधि अनुसंधान]] दोनों में शोध का विषय हैं, क्योंकि उनके निर्माण में नियमितता कई प्रतीत होने वाले असंबद्ध परिवारों की समस्याओं का विश्लेषण और समाधान करने के लिए एक सामान्य आधार प्रदान करती है। [[बाधा संतुष्टि की जटिलता]], एक उचित समय में हल करने के लिए [[ heuristics ]] और कॉम्बीनेटरियल खोज विधियों के संयोजन की आवश्यकता होती है। [[बाधा प्रोग्रामिंग]] (सीपी) अनुसंधान का क्षेत्र है जो विशेष रूप से इस प्रकार की समस्याओं से निपटने पर केंद्रित है।<ref>{{Cite book|title=Constraint Networks: Techniques and Algorithms|last=Lecoutre|first=Christophe|publisher=Wiley|year=2013|isbn=978-1-118-61791-5|pages=26}}</ref><ref>{{Cite web|url=http://www.springer.com/computer/ai/journal/10601|title=Constraints – incl. option to publish open access|website=springer.com|language=en|access-date=2019-10-03}}</ref> इसके अतिरिक्त, [[बूलियन संतुष्टि समस्या]] (एसएटी), संतुष्टि मोडुलो सिद्धांत (एसएमटी), [[मिश्रित पूर्णांक प्रोग्रामिंग]] (एमआईपी) और [[उत्तर सेट प्रोग्रामिंग]] (एएसपी) बाधा संतुष्टि समस्या के विशेष रूपों के समाधान पर ध्यान केंद्रित करने वाले शोध के सभी क्षेत्र हैं।
+बाधा संतुष्टि समस्याएं (सीएसपी) गणितीय प्रश्न हैं जिन्हें वस्तुओं के एक सेट के रूप में परिभाषित किया गया है जिनके [[राज्य (कंप्यूटर विज्ञान)]] को कई बाधाओं (गणित) या [[सीमा (गणित)]] को पूरा करना चाहिए। सीएसपी परिमित बाधाओं के एक सजातीय संग्रह के रूप में एक समस्या में संस्थाओं का प्रतिनिधित्व करते हैं, जो कि बाधा संतुष्टि विधियों द्वारा हल किया जाता है। सीएसपी [[ कृत्रिम होशियारी ]] और [[गतिविधि अनुसंधान]] दोनों में शोध का विषय हैं, क्योंकि उनके निर्माण में नियमितता कई प्रतीत होने वाले असंबद्ध परिवारों की समस्याओं का विश्लेषण और समाधान करने के लिए एक सामान्य आधार प्रदान करती है। [[बाधा संतुष्टि की जटिलता]], एक उचित समय में हल करने के लिए [[ heuristics | ह्यूरिस्टिक्स]] और मिश्रित खोज विधियों के संयोजन की आवश्यकता होती है। [[बाधा प्रोग्रामिंग]] (सीपी) अनुसंधान का क्षेत्र है जो विशेष रूप से इस प्रकार की समस्याओं से निपटने पर केंद्रित है।<ref>{{Cite book|title=Constraint Networks: Techniques and Algorithms|last=Lecoutre|first=Christophe|publisher=Wiley|year=2013|isbn=978-1-118-61791-5|pages=26}}</ref><ref>{{Cite web|url=http://www.springer.com/computer/ai/journal/10601|title=Constraints – incl. option to publish open access|website=springer.com|language=en|access-date=2019-10-03}}</ref> इसके अतिरिक्त, [[बूलियन संतुष्टि समस्या]] (एसएटी), संतुष्टि मोडुलो सिद्धांत (एसएमटी), [[मिश्रित पूर्णांक प्रोग्रामिंग]] (एमआईपी) और [[उत्तर सेट प्रोग्रामिंग]] (एएसपी) बाधा संतुष्टि समस्या के विशेष रूपों के समाधान पर ध्यान केंद्रित करने वाले शोध के सभी क्षेत्र हैं।
-समस्याओं के उदाहरण जिन्हें एक बाधा संतुष्टि समस्या के रूप में प्रतिरूपित किया जा सकता है उनमें शामिल हैं:
+समस्याओं के उदाहरण जिन्हें एक बाधा संतुष्टि समस्या के रूप में प्रतिरूपित किया जा सकता है उनमें सम्मिलित हैं:
 * [[अनुमान टाइप करें]]<ref>Chandra, Satish, et al. "[https://cs.drexel.edu/~csgordon/papers/oopsla16.pdf Type inference for static compilation of JavaScript]." ACM SIGPLAN Notices 51.10 (2016): 410-429.</ref><ref>Jim, Trevor, and Jens Palsberg. "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.886&rep=rep1&type=pdf Type inference in systems of recursive types with subtyping]." Available on authors’ web page (1999).</ref>
@@ Line 12: / Line 12: @@
 * [[सुडोकू]], [[क्रॉसवर्ड]], [[फूटोशिकी]], [[ तंबाकू से होने वाली बीमारी ]] (क्रॉस सम्स), [[न्यूम्ब्रिक्स]], हिडाटो और कई अन्य [[तर्क पहेली]]
-इन्हें अक्सर बाधा प्रोग्रामिंग, एएसपी, बूलियन एसएटी और एसएमटी सॉल्वर के ट्यूटोरियल के साथ प्रदान किया जाता है। सामान्य मामले में, बाधा की समस्याएं बहुत कठिन हो सकती हैं, और इनमें से कुछ सरल प्रणालियों में अभिव्यक्त नहीं हो सकती हैं। वास्तविक जीवन के उदाहरणों में [[स्वचालित योजना]],<ref name="GhallabNau2004">{{cite book|author1=Malik Ghallab|author2=Dana Nau|author3=Paolo Traverso|title=Automated Planning: Theory and Practice|url=https://books.google.com/books?id=uYnpze57MSgC&q=%22constraint+satisfaction%22&pg=PP1|date=21 May 2004|publisher=Elsevier|isbn=978-0-08-049051-9|pages=1–}}</ref><ref>[http://www.cs.st-andrews.ac.uk/~ianm/docs/Thesis.ppt Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning], {{webarchive|url=https://web.archive.org/web/20090206055207/http://www.cs.st-andrews.ac.uk/~ianm/docs/Thesis.ppt |date=2009-02-06 }} Ian Miguel – slides.</ref> [[शाब्दिक असंबद्धता]],<ref>Demetriou, George C. "[http://www.aclweb.org/anthology/E93-1051 Lexical disambiguation using constraint handling in Prolog (CHIP)]." Proceedings of the sixth conference on European chapter of the Association for Computational Linguistics. Association for Computational Linguistics, 1993.</ref><ref>MacDonald, Maryellen C., and Mark S. Seidenberg. "[https://web.archive.org/web/20180325105726/https://pdfs.semanticscholar.org/a73e/53c44f1e998c5a03b9cbac9e0e16d5b09e77.pdf Constraint satisfaction accounts of lexical and sentence comprehension]." Handbook of Psycholinguistics (Second Edition). 2006. 581–611.</ref> संगीतशास्त्र,<ref>Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. "[http://www.jatit.org/volumes/Vol86No2/17Vol86No2.pdf GELISP: A FRAMEWORK TO REPRESENT MUSICAL CONSTRAINT SATISFACTION PROBLEMS AND SEARCH STRATEGIES]." Journal of Theoretical and Applied Information Technology 86 (2). 2016. 327–331.</ref> कॉन्फ़िगर करें, मूल्य और उद्धरण<ref>''Applying constraint satisfaction approach to solve product configuration problems with cardinality-based configuration rules'', Dong Yang & Ming Dong, [[Journal of Intelligent Manufacturing]] volume 24, pages99–111 (2013)</ref> और संसाधन आवंटन।<ref>Modi, Pragnesh Jay, et al. "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.8697&rep=rep1&type=pdf A dynamic distributed constraint satisfaction approach to resource allocation]." International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg, 2001.</ref>
+इन्हें अधिकांशतः बाधा प्रोग्रामिंग, एएसपी, बूलियन एसएटी और एसएमटी सॉल्वर के ट्यूटोरियल के साथ प्रदान किया जाता है। सामान्य स्थितियों में, बाधा की समस्याएं बहुत कठिन हो सकती हैं, और इनमें से कुछ सरल प्रणालियों में अभिव्यक्त नहीं हो सकती हैं। वास्तविक जीवन के उदाहरणों में [[स्वचालित योजना]],<ref name="GhallabNau2004">{{cite book|author1=Malik Ghallab|author2=Dana Nau|author3=Paolo Traverso|title=Automated Planning: Theory and Practice|url=https://books.google.com/books?id=uYnpze57MSgC&q=%22constraint+satisfaction%22&pg=PP1|date=21 May 2004|publisher=Elsevier|isbn=978-0-08-049051-9|pages=1–}}</ref><ref>[http://www.cs.st-andrews.ac.uk/~ianm/docs/Thesis.ppt Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning], {{webarchive|url=https://web.archive.org/web/20090206055207/http://www.cs.st-andrews.ac.uk/~ianm/docs/Thesis.ppt |date=2009-02-06 }} Ian Miguel – slides.</ref> [[शाब्दिक असंबद्धता]],<ref>Demetriou, George C. "[http://www.aclweb.org/anthology/E93-1051 Lexical disambiguation using constraint handling in Prolog (CHIP)]." Proceedings of the sixth conference on European chapter of the Association for Computational Linguistics. Association for Computational Linguistics, 1993.</ref><ref>MacDonald, Maryellen C., and Mark S. Seidenberg. "[https://web.archive.org/web/20180325105726/https://pdfs.semanticscholar.org/a73e/53c44f1e998c5a03b9cbac9e0e16d5b09e77.pdf Constraint satisfaction accounts of lexical and sentence comprehension]." Handbook of Psycholinguistics (Second Edition). 2006. 581–611.</ref> संगीतशास्त्र,<ref>Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. "[http://www.jatit.org/volumes/Vol86No2/17Vol86No2.pdf GELISP: A FRAMEWORK TO REPRESENT MUSICAL CONSTRAINT SATISFACTION PROBLEMS AND SEARCH STRATEGIES]." Journal of Theoretical and Applied Information Technology 86 (2). 2016. 327–331.</ref> '''कॉन्फ़िगर करें''', मूल्य और उद्धरण<ref>''Applying constraint satisfaction approach to solve product configuration problems with cardinality-based configuration rules'', Dong Yang & Ming Dong, [[Journal of Intelligent Manufacturing]] volume 24, pages99–111 (2013)</ref> और संसाधन आवंटन सम्मिलित   है।<ref>Modi, Pragnesh Jay, et al. "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.8697&rep=rep1&type=pdf A dynamic distributed constraint satisfaction approach to resource allocation]." International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg, 2001.</ref>
-सीएसपी के समाधान के अस्तित्व को [[निर्णय समस्या]] के रूप में देखा जा सकता है। यह एक समाधान खोजने के द्वारा तय किया जा सकता है, या संपूर्ण खोज के बाद एक समाधान खोजने में विफल हो सकता है (स्टोकेस्टिक एल्गोरिदम आमतौर पर कभी भी एक संपूर्ण निष्कर्ष पर नहीं पहुंचते हैं, जबकि निर्देशित खोज अक्सर पर्याप्त छोटी समस्याओं पर होती है)। कुछ मामलों में सीएसपी को कुछ अन्य गणितीय अनुमान प्रक्रिया के माध्यम से समाधान के लिए जाना जा सकता है।
+सीएसपी के समाधान के अस्तित्व को [[निर्णय समस्या]] के रूप में देखा जा सकता है। यह एक समाधान खोजने के द्वारा तय किया जा सकता है, या संपूर्ण खोज के बाद एक समाधान खोजने में विफल हो सकता है (स्टोकेस्टिक एल्गोरिदम सामान्यतः पर कभी भी एक संपूर्ण निष्कर्ष पर नहीं पहुंचते हैं, जबकि निर्देशित खोज अधिकांशतः पर्याप्त छोटी समस्याओं पर होती है)। कुछ स्थितियों में सीएसपी को कुछ अन्य गणितीय अनुमान प्रक्रिया के माध्यम से समाधान के लिए जाना जा सकता है।
 == औपचारिक परिभाषा ==
@@ Line 21: / Line 22: @@
 * <math>C = \{C_1, \ldots, C_m\}</math> बाधाओं का एक समूह है।
 प्रत्येक चर <math>X_i</math> गैर-खाली डोमेन में मान ले सकता है <math>D_i</math>.
-हर विवशता <math>C_j \in C</math> बदले में एक जोड़ी है <math>\langle t_j,R_j \rangle</math>, कहाँ <math>t_j \subset X</math> का उपसमुच्चय है <math>k</math> चर और <math>R_j</math> एक है <math>k</math>डोमेन के संबंधित उपसमुच्चय पर -अरी [[संबंध (गणित)]]। <math>D_j</math>. वेरिएबल्स का मूल्यांकन डोमेन के संबंधित सबसेट में वेरिएबल्स के एक सबसेट से मूल्यों के एक विशेष सेट के लिए एक फ़ंक्शन है। एक विकास <math>v</math> एक बाधा को संतुष्ट करता है <math>\langle t_j, R_j \rangle</math> यदि मान चर को सौंपा गया है <math>t_j</math> संबंध को संतुष्ट करता है <math>R_j</math>.
-एक मूल्यांकन सुसंगत है यदि यह किसी भी बाधा का उल्लंघन नहीं करता है। एक मूल्यांकन पूर्ण होता है यदि इसमें सभी चर शामिल होते हैं। एक मूल्यांकन एक समाधान है यदि यह सुसंगत और पूर्ण है; इस तरह के मूल्यांकन को बाधा संतुष्टि समस्या को हल करने के लिए कहा जाता है।
+हर विवशता <math>C_j \in C</math> बदले में एक जोड़ी है <math>\langle t_j,R_j \rangle</math>, कहाँ <math>t_j \subset X</math> का उपसमुच्चय है <math>k</math> चर और <math>R_j</math> एक है <math>k</math>डोमेन के संबंधित उपसमुच्चय पर -अरी [[संबंध (गणित)]]। <math>D_j</math>. वेरिएबल्स का मूल्यांकन डोमेन के संबंधित सबसेट में वेरिएबल्स के एक सबसेट से मूल्यों के एक विशेष सेट के लिए एक फलन है। एक विकास <math>v</math> एक बाधा को संतुष्ट करता है <math>\langle t_j, R_j \rangle</math> यदि मान चर को सौंपा गया है <math>t_j</math> संबंध को संतुष्ट करता है <math>R_j</math>.
+एक मूल्यांकन सुसंगत है यदि यह किसी भी बाधा का उल्लंघन नहीं करता है। एक मूल्यांकन पूर्ण होता है यदि इसमें सभी चर सम्मिलित होते हैं। एक मूल्यांकन एक समाधान है यदि यह सुसंगत और पूर्ण है; इस तरह के मूल्यांकन को बाधा संतुष्टि समस्या को हल करने के लिए कहा जाता है।
 == समाधान ==
-परिमित डोमेन पर बाधा संतुष्टि समस्याओं को आम तौर पर खोज एल्गोरिद्म के एक रूप का उपयोग करके हल किया जाता है। सबसे अधिक उपयोग की जाने वाली तकनीकें [[ बैक ट्रैकिंग ]], [[बाधा प्रसार]] और [[स्थानीय खोज (अनुकूलन)]] के प्रकार हैं। इन तकनीकों को भी अक्सर संयुक्त किया जाता है, जैसा कि [[बहुत बड़े पैमाने पर पड़ोस की खोज]] पद्धति में होता है, और वर्तमान शोध में अन्य प्रौद्योगिकियां शामिल होती हैं जैसे [[रैखिक प्रोग्रामिंग]]।<ref>{{Cite book|title=Hybrid optimization : the ten years of CPAIOR|date=2011|publisher=Springer|others=Milano, Michela., Van Hentenryck, Pascal., International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems.|isbn=9781441916440|location=New York|oclc=695387020}}</ref>
+परिमित डोमेन पर बाधा संतुष्टि समस्याओं को आम तौर पर खोज एल्गोरिद्म के एक रूप का उपयोग करके हल किया जाता है। सबसे अधिक उपयोग की जाने वाली तकनीकें [[ बैक ट्रैकिंग ]], [[बाधा प्रसार]] और [[स्थानीय खोज (अनुकूलन)]] के प्रकार हैं। इन तकनीकों को भी अधिकांशतः संयुक्त किया जाता है, जैसा कि [[बहुत बड़े पैमाने पर पड़ोस की खोज]] पद्धति में होता है, और वर्तमान शोध में अन्य प्रौद्योगिकियां सम्मिलित होती हैं जैसे [[रैखिक प्रोग्रामिंग]]।<ref>{{Cite book|title=Hybrid optimization : the ten years of CPAIOR|date=2011|publisher=Springer|others=Milano, Michela., Van Hentenryck, Pascal., International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems.|isbn=9781441916440|location=New York|oclc=695387020}}</ref>
-बैकट्रैकिंग एक पुनरावर्ती एल्गोरिथम है। यह चर के आंशिक असाइनमेंट को बनाए रखता है। प्रारंभ में, सभी चर असाइन नहीं किए गए हैं। प्रत्येक चरण में, एक चर चुना जाता है, और सभी संभावित मान बदले में इसे सौंपे जाते हैं। प्रत्येक मूल्य के लिए, बाधाओं के साथ आंशिक असाइनमेंट की निरंतरता की जाँच की जाती है; संगति के मामले में, एक [[प्रत्यावर्तन]] कॉल किया जाता है। जब सभी मानों का प्रयास किया गया है, तो एल्गोरिदम बैकट्रैक करता है। इस मूल बैकट्रैकिंग एल्गोरिथ्म में, संगति को उन सभी बाधाओं की संतुष्टि के रूप में परिभाषित किया गया है जिनके चर सभी असाइन किए गए हैं। बैकट्रैकिंग के कई रूप मौजूद हैं। [[बैकमार्किंग]] स्थिरता की जाँच की दक्षता में सुधार करता है। [[ पीछे कूदना ]] कुछ मामलों में एक से अधिक वेरिएबल को बैकट्रैक करके खोज के हिस्से को बचाने की अनुमति देता है। बाधा सीखने से नए अवरोधों का पता चलता है और सहेजता है जिनका उपयोग बाद में खोज के भाग से बचने के लिए किया जा सकता है। [[लुक-फॉरवर्ड (बैकट्रैकिंग)]] | लुक-फॉरवर्ड का उपयोग अक्सर बैकट्रैकिंग में एक चर या मान को चुनने के प्रभावों को देखने के प्रयास में किया जाता है, इस प्रकार कभी-कभी अग्रिम में निर्धारित किया जाता है कि कोई उप-समस्या संतोषजनक या असंतोषजनक है।
+बैकट्रैकिंग एक पुनरावर्ती एल्गोरिथम है। यह चर के आंशिक असाइनमेंट को बनाए रखता है। प्रारंभ में, सभी चर असाइन नहीं किए गए हैं। प्रत्येक चरण में, एक चर चुना जाता है, और सभी संभावित मान बदले में इसे सौंपे जाते हैं। प्रत्येक मूल्य के लिए, बाधाओं के साथ आंशिक असाइनमेंट की निरंतरता की जाँच की जाती है; संगति के स्थितियों में, एक [[प्रत्यावर्तन]] कॉल किया जाता है। जब सभी मानों का प्रयास किया गया है, तो एल्गोरिदम बैकट्रैक करता है। इस मूल बैकट्रैकिंग एल्गोरिथ्म में, संगति को उन सभी बाधाओं की संतुष्टि के रूप में परिभाषित किया गया है जिनके चर सभी असाइन किए गए हैं। बैकट्रैकिंग के कई रूप मौजूद हैं। [[बैकमार्किंग]] स्थिरता की जाँच की दक्षता में सुधार करता है। [[ पीछे कूदना | पीछे कूदना]] कुछ स्थितियों में एक से अधिक वेरिएबल को बैकट्रैक करके खोज के हिस्से को बचाने की अनुमति देता है। बाधा सीखने से नए अवरोधों का पता चलता है और सहेजता है जिनका उपयोग बाद में खोज के भाग से बचने के लिए किया जा सकता है। [[लुक-फॉरवर्ड (बैकट्रैकिंग)]] | लुक-फॉरवर्ड का उपयोग अधिकांशतः बैकट्रैकिंग में एक चर या मान को चुनने के प्रभावों को देखने के प्रयास में किया जाता है, इस प्रकार कभी-कभी अग्रिम में निर्धारित किया जाता है कि कोई उप-समस्या संतोषजनक या असंतोषजनक है।
-बाधा प्रसार तकनीक एक बाधा संतुष्टि समस्या को संशोधित करने के लिए उपयोग की जाने वाली विधियाँ हैं। अधिक सटीक रूप से, वे ऐसे तरीके हैं जो स्थानीय स्थिरता के एक रूप को लागू करते हैं, जो चर और/या बाधाओं के समूह की स्थिरता से संबंधित शर्तें हैं। बाधा प्रसार के विभिन्न उपयोग हैं। सबसे पहले, यह एक समस्या को समतुल्य में बदल देता है लेकिन आमतौर पर हल करना आसान होता है। दूसरा, यह समस्याओं की संतुष्टि या असंतोषजनक साबित हो सकता है। यह सामान्य रूप से होने की गारंटी नहीं है; हालाँकि, यह हमेशा कुछ प्रकार की बाधा प्रसार और/या कुछ प्रकार की समस्याओं के लिए होता है। [[स्थानीय संगति]] के सर्वाधिक ज्ञात और उपयोग किए जाने वाले रूप चाप संगति, हाइपर-आर्क संगति और पथ संगति हैं। सबसे लोकप्रिय बाधा प्रचार विधि एसी [[एसी-3 एल्गोरिथम]] है, जो आर्क स्थिरता को लागू करती है।
+बाधा प्रसार तकनीक एक बाधा संतुष्टि समस्या को संशोधित करने के लिए उपयोग की जाने वाली विधियाँ हैं। अधिक सटीक रूप से, वे ऐसे तरीके हैं जो स्थानीय स्थिरता के एक रूप को लागू करते हैं, जो चर और/या बाधाओं के समूह की स्थिरता से संबंधित शर्तें हैं। बाधा प्रसार के विभिन्न उपयोग हैं। सबसे पहले, यह एक समस्या को समतुल्य में बदल देता है लेकिन सामान्यतः पर हल करना आसान होता है। दूसरा, यह समस्याओं की संतुष्टि या असंतोषजनक साबित हो सकता है। यह सामान्य रूप से होने की गारंटी नहीं है; हालाँकि, यह हमेशा कुछ प्रकार की बाधा प्रसार और/या कुछ प्रकार की समस्याओं के लिए होता है। [[स्थानीय संगति]] के सर्वाधिक ज्ञात और उपयोग किए जाने वाले रूप चाप संगति, हाइपर-आर्क संगति और पथ संगति हैं। सबसे लोकप्रिय बाधा प्रचार विधि एसी [[एसी-3 एल्गोरिथम]] है, जो आर्क स्थिरता को लागू करती है।
 स्थानीय खोज (अनुकूलन) विधियाँ अपूर्ण संतुष्टि एल्गोरिथम हैं। वे किसी समस्या का हल खोज सकते हैं, लेकिन समस्या संतोषजनक होने पर भी वे असफल हो सकते हैं। वे चरों पर एक पूर्ण असाइनमेंट में पुनरावृत्त रूप से सुधार करके काम करते हैं। इस असाइनमेंट द्वारा संतुष्ट बाधाओं की संख्या में वृद्धि के समग्र उद्देश्य के साथ, प्रत्येक चरण में, चर की एक छोटी संख्या को मूल्य में बदल दिया जाता है। [[न्यूनतम-संघर्ष एल्गोरिथम]] सीएसपी के लिए विशिष्ट एक स्थानीय खोज एल्गोरिथम है और यह उस सिद्धांत पर आधारित है। व्यवहार में, स्थानीय खोज अच्छी तरह से काम करती प्रतीत होती है जब ये परिवर्तन यादृच्छिक विकल्पों से भी प्रभावित होते हैं। स्थानीय खोज के साथ खोज का एकीकरण विकसित किया गया है, जिससे हाइब्रिड एल्गोरिद्म (प्रतिबंध संतुष्टि) प्राप्त होता है।
@@ Line 36: / Line 39: @@
 === निर्णय समस्याएं ===
-सीएसपी का अध्ययन [[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[परिमित मॉडल सिद्धांत]] में भी किया जाता है। एक महत्वपूर्ण प्रश्न यह है कि क्या संबंधों के प्रत्येक सेट के लिए, सभी सीएसपी का सेट जिसे केवल उस सेट से चुने गए संबंधों का उपयोग करके दर्शाया जा सकता है, या तो [[पी (जटिलता)]] या एनपी-पूर्ण में है। यदि ऐसा द्विभाजन प्रमेय सत्य है, तो सीएसपी [[एनपी (जटिलता)]] के सबसे बड़े ज्ञात उपसमुच्चयों में से एक प्रदान करते हैं जो [[एनपी-मध्यवर्ती]] समस्याओं से बचा जाता है, जिसका अस्तित्व लेडनर के प्रमेय द्वारा इस धारणा के तहत प्रदर्शित किया गया था कि पी बनाम एनपी समस्या|पी ≠ एनपी। शेफर का द्विभाजन प्रमेय उस मामले को संभालता है जब सभी उपलब्ध संबंध [[बूलियन ऑपरेटर (बूलियन बीजगणित)]] होते हैं, जो कि डोमेन आकार 2 के लिए होता है। शेफर के द्विभाजन प्रमेय को हाल ही में संबंधों के एक बड़े वर्ग के लिए सामान्यीकृत किया गया था।<ref>{{Cite book| last1 = Bodirsky | first1 = Manuel| last2 = Pinsker | first2 = Michael| doi = 10.1145/1993636.1993724 | contribution = Schaefer's theorem for graphs | publisher= [[Association for Computing Machinery]]| title = Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC '11)| pages = 655–664 | year = 2011 | isbn = 978-1-4503-0691-1| arxiv        = 1011.2894| bibcode      = 2010arXiv1011.2894B| title-link = Symposium on Theory of Computing| s2cid = 47097319}}</ref>
+सीएसपी का अध्ययन [[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[परिमित मॉडल सिद्धांत]] में भी किया जाता है। एक महत्वपूर्ण प्रश्न यह है कि क्या संबंधों के प्रत्येक सेट के लिए, सभी सीएसपी का सेट जिसे केवल उस सेट से चुने गए संबंधों का उपयोग करके दर्शाया जा सकता है, या तो [[पी (जटिलता)]] या एनपी-पूर्ण में है। यदि ऐसा द्विभाजन प्रमेय सत्य है, तो सीएसपी [[एनपी (जटिलता)]] के सबसे बड़े ज्ञात उपसमुच्चयों में से एक प्रदान करते हैं जो [[एनपी-मध्यवर्ती]] समस्याओं से बचा जाता है, जिसका अस्तित्व लेडनर के प्रमेय द्वारा इस धारणा के तहत प्रदर्शित किया गया था कि पी बनाम एनपी समस्या|पी ≠ एनपी। शेफर का द्विभाजन प्रमेय उस स्थितियों को संभालता है जब सभी उपलब्ध संबंध [[बूलियन ऑपरेटर (बूलियन बीजगणित)]] होते हैं, जो कि डोमेन आकार 2 के लिए होता है। शेफर के द्विभाजन प्रमेय को हाल ही में संबंधों के एक बड़े वर्ग के लिए सामान्यीकृत किया गया था।<ref>{{Cite book| last1 = Bodirsky | first1 = Manuel| last2 = Pinsker | first2 = Michael| doi = 10.1145/1993636.1993724 | contribution = Schaefer's theorem for graphs | publisher= [[Association for Computing Machinery]]| title = Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC '11)| pages = 655–664 | year = 2011 | isbn = 978-1-4503-0691-1| arxiv        = 1011.2894| bibcode      = 2010arXiv1011.2894B| title-link = Symposium on Theory of Computing| s2cid = 47097319}}</ref>
-सीएसपी के अधिकांश वर्ग जिन्हें ट्रैक्टेबल के रूप में जाना जाता है, वे हैं जहां बाधाओं के [[ hypergraph ]] ने [[ पेड़ की चौड़ाई ]] को सीमित कर दिया है (और बाधा संबंधों के सेट पर कोई प्रतिबंध नहीं है), या जहां बाधाओं का मनमाना रूप है, लेकिन अनिवार्य रूप से गैर-एकात्मक बहुरूपता मौजूद हैं{{Clarify|date=February 2009}} बाधा संबंधों के सेट का।
+सीएसपी के अधिकांश वर्ग जिन्हें ट्रैक्टेबल के रूप में जाना जाता है, वे हैं जहां बाधाओं के [[ hypergraph | hypergraph]] ने [[ पेड़ की चौड़ाई | पेड़ की चौड़ाई]] को सीमित कर दिया है (और बाधा संबंधों के सेट पर कोई प्रतिबंध नहीं है), या जहां बाधाओं का मनमाना रूप है, लेकिन अनिवार्य रूप से गैर-एकात्मक बहुरूपता मौजूद हैं{{Clarify|date=February 2009}} बाधा संबंधों के सेट का।
 प्रत्येक सीएसपी को संयोजन क्वेरी रोकथाम समस्या के रूप में भी माना जा सकता है।<ref>{{Cite journal| last1 = Kolaitis| first1 = Phokion G.| last2 = Vardi| first2 = Moshe Y.| author-link2 = Moshe Y. Vardi| title = संयोजन-प्रश्न नियंत्रण और बाधा संतुष्टि| journal = [[Journal of Computer and System Sciences]]| volume = 61| issue = 2| pages = 302–332| year = 2000| doi = 10.1006/jcss.2000.1713 | doi-access = free}}</ref>
@@ Line 43: / Line 47: @@
 === कार्य समस्याएं ===
-इसी तरह की स्थिति कार्यात्मक वर्गों [[एफपी (जटिलता)]] और तीव्र-पी | # पी के बीच मौजूद है। लेडनर के प्रमेय के सामान्यीकरण से, न तो FP और न ही Sharp-P-पूर्ण|#P-पूर्ण जब तक FP ≠ #P है, तब तक समस्याएँ हैं। जैसा कि निर्णय मामले में, #CSP में एक समस्या संबंधों के एक समूह द्वारा परिभाषित की जाती है। प्रत्येक समस्या एक [[बूलियन तर्क]] सूत्र को इनपुट के रूप में लेती है और कार्य संतोषजनक असाइनमेंट की संख्या की गणना करना है। इसे बड़े डोमेन आकार का उपयोग करके और प्रत्येक संतोषजनक असाइनमेंट के लिए एक भार जोड़कर और इन भारों के योग की गणना करके इसे और सामान्यीकृत किया जा सकता है। यह ज्ञात है कि कोई भी जटिल भारित #सीएसपी समस्या या तो एफपी या #पी-हार्ड में है।<ref>{{Cite conference| last1 = Cai | first1 = Jin-Yi| last2 = Chen | first2 = Xi| doi = 10.1145/2213977.2214059 | title = जटिल भार के साथ सीएसपी की गिनती की जटिलता| book-title = [[Symposium on Theory of Computing|Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12)]] | pages = 909–920 | year = 2012 | isbn = 978-1-4503-1245-5| arxiv        = 1111.2384| s2cid = 53245129}}</ref>
+इसी तरह की स्थिति कार्यात्मक वर्गों [[एफपी (जटिलता)]] और तीव्र-पी | # पी के बीच मौजूद है। लेडनर के प्रमेय के सामान्यीकरण से, न तो FP और न ही Sharp-P-पूर्ण|#P-पूर्ण जब तक FP ≠ #P है, तब तक समस्याएँ हैं। जैसा कि निर्णय स्थितियों में, #CSP में एक समस्या संबंधों के एक समूह द्वारा परिभाषित की जाती है। प्रत्येक समस्या एक [[बूलियन तर्क]] सूत्र को इनपुट के रूप में लेती है और कार्य संतोषजनक असाइनमेंट की संख्या की गणना करना है। इसे बड़े डोमेन आकार का उपयोग करके और प्रत्येक संतोषजनक असाइनमेंट के लिए एक भार जोड़कर और इन भारों के योग की गणना करके इसे और सामान्यीकृत किया जा सकता है। यह ज्ञात है कि कोई भी जटिल भारित #सीएसपी समस्या या तो एफपी या #पी-हार्ड में है।<ref>{{Cite conference| last1 = Cai | first1 = Jin-Yi| last2 = Chen | first2 = Xi| doi = 10.1145/2213977.2214059 | title = जटिल भार के साथ सीएसपी की गिनती की जटिलता| book-title = [[Symposium on Theory of Computing|Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12)]] | pages = 909–920 | year = 2012 | isbn = 978-1-4503-1245-5| arxiv        = 1111.2384| s2cid = 53245129}}</ref>
@@ Line 58: / Line 62: @@
 === गतिशील सीएसपी ===
-गतिशील सीएसपी<ref>Dechter, R. and Dechter, A., [http://www.ics.uci.edu/%7Ecsp/r5.pdf Belief Maintenance in Dynamic Constraint Networks] {{Webarchive|url=https://web.archive.org/web/20121117042241/http://www.ics.uci.edu/%7Ecsp/r5.pdf |date=2012-11-17 }} In Proc. of AAAI-88, 37–42.</ref> (DCSPs) तब उपयोगी होते हैं जब किसी समस्या के मूल सूत्रीकरण को किसी तरह से बदल दिया जाता है, आमतौर पर क्योंकि विचार करने के लिए बाधाओं का सेट पर्यावरण के कारण विकसित होता है।<ref>[http://www.aaai.org/Papers/AAAI/1994/AAAI94-302.pdf Solution reuse in dynamic constraint satisfaction problems], Thomas Schiex</ref> डीसीएसपी को स्थिर सीएसपी के अनुक्रम के रूप में देखा जाता है, प्रत्येक पिछले एक का एक परिवर्तन है जिसमें चर और बाधाओं को जोड़ा जा सकता है (प्रतिबंध) या हटाया जा सकता है (छूट)। समस्या के प्रारंभिक योगों में मिली जानकारी का उपयोग अगले वाले को परिष्कृत करने के लिए किया जा सकता है। हल करने की विधि को उस तरीके के अनुसार वर्गीकृत किया जा सकता है जिसमें सूचना स्थानांतरित की जाती है:
+गतिशील सीएसपी<ref>Dechter, R. and Dechter, A., [http://www.ics.uci.edu/%7Ecsp/r5.pdf Belief Maintenance in Dynamic Constraint Networks] {{Webarchive|url=https://web.archive.org/web/20121117042241/http://www.ics.uci.edu/%7Ecsp/r5.pdf |date=2012-11-17 }} In Proc. of AAAI-88, 37–42.</ref> (DCSPs) तब उपयोगी होते हैं जब किसी समस्या के मूल सूत्रीकरण को किसी तरह से बदल दिया जाता है, सामान्यतः पर क्योंकि विचार करने के लिए बाधाओं का सेट पर्यावरण के कारण विकसित होता है।<ref>[http://www.aaai.org/Papers/AAAI/1994/AAAI94-302.pdf Solution reuse in dynamic constraint satisfaction problems], Thomas Schiex</ref> डीसीएसपी को स्थिर सीएसपी के अनुक्रम के रूप में देखा जाता है, प्रत्येक पिछले एक का एक परिवर्तन है जिसमें चर और बाधाओं को जोड़ा जा सकता है (प्रतिबंध) या हटाया जा सकता है (छूट)। समस्या के प्रारंभिक योगों में मिली जानकारी का उपयोग अगले वाले को परिष्कृत करने के लिए किया जा सकता है। हल करने की विधि को उस तरीके के अनुसार वर्गीकृत किया जा सकता है जिसमें सूचना स्थानांतरित की जाती है:
 * भविष्यवाणी: अनुक्रम में पिछले सीएसपी के लिए पाया गया समाधान वर्तमान सीएसपी के संकल्प को खरोंच से मार्गदर्शन करने के लिए हेयूरिस्टिक्स के रूप में उपयोग किया जाता है।
 * स्थानीय मरम्मत: प्रत्येक सीएसपी की गणना पिछले एक के आंशिक समाधान से शुरू की जाती है और स्थानीय खोज (अनुकूलन) के साथ असंगत बाधाओं की मरम्मत की जाती है।
@@ Line 64: / Line 68: @@
 === लचीला सीएसपी ===
-क्लासिक सीएसपी बाधाओं को कठिन मानते हैं, जिसका अर्थ है कि वे अनिवार्य हैं (प्रत्येक समाधान को उन सभी को संतुष्ट करना चाहिए) और अनम्य (इस अर्थ में कि उन्हें पूरी तरह से संतुष्ट होना चाहिए या फिर उनका पूरी तरह से उल्लंघन किया जाना चाहिए)। 'लचीला सीएसपी उन धारणाओं को आराम देता है, आंशिक रूप से बाधाओं को आराम देता है और समाधान को उन सभी का पालन नहीं करने देता है। यह [[वरीयता-आधारित योजना]] में प्राथमिकताओं के समान है। कुछ प्रकार के लचीले सीएसपी में शामिल हैं:
+क्लासिक सीएसपी बाधाओं को कठिन मानते हैं, जिसका अर्थ है कि वे अनिवार्य हैं (प्रत्येक समाधान को उन सभी को संतुष्ट करना चाहिए) और अनम्य (इस अर्थ में कि उन्हें पूरी तरह से संतुष्ट होना चाहिए या फिर उनका पूरी तरह से उल्लंघन किया जाना चाहिए)। 'लचीला सीएसपी उन धारणाओं को आराम देता है, आंशिक रूप से बाधाओं को आराम देता है और समाधान को उन सभी का पालन नहीं करने देता है। यह [[वरीयता-आधारित योजना]] में प्राथमिकताओं के समान है। कुछ प्रकार के लचीले सीएसपी में सम्मिलित हैं:
 * मैक्स-सीएसपी, जहां कई बाधाओं का उल्लंघन करने की अनुमति है, और समाधान की गुणवत्ता को संतुष्ट बाधाओं की संख्या से मापा जाता है।
 * [[भारित बाधा संतुष्टि समस्या]], एक MAX-CSP जिसमें एक बाधा के प्रत्येक उल्लंघन को पूर्वनिर्धारित वरीयता के अनुसार भारित किया जाता है। इस प्रकार अधिक वजन के साथ संतोषजनक बाधा को प्राथमिकता दी जाती है।

Anonymous

Search

बाधा संतुष्टि की समस्या: Difference between revisions

Namespaces

More

Page actions

Revision as of 11:01, 7 March 2023

Contents

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

समाधान

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

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

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

वेरिएंट

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

लचीला सीएसपी

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

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

बाधा संतुष्टि की समस्या: Difference between revisions

Revision as of 11:01, 7 March 2023

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

समाधान

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

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

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

वेरिएंट

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

लचीला सीएसपी

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

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories