कन्सट्रैन्ट सटिस्फैक्शन

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

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

एक सामान्य समस्या के रूप में बाधा संतुष्टि 1970 के दशक में कृत्रिम बुद्धिमत्ता के क्षेत्र में उत्पन्न हुई (उदाहरण के लिए देखें)। (Laurière 1978)). हालाँकि, जब बाधाओं को समानताओं को परिभाषित करने वाले बहुभिन्नरूपी रैखिक समीकरणों के रूप में व्यक्त किया जाता है, तो यह क्षेत्र 19वीं शताब्दी में जोसेफ फूरियर के पास वापस चला जाता है: 1946 में जॉर्ज डेंजिग के रैखिक प्रोग्रामिंग (गणितीय अनुकूलन का एक विशेष मामला) के लिए सिम्प्लेक्स एल्गोरिथम के आविष्कार ने सैकड़ों चर वाली समस्याओं के संभावित समाधान निर्धारित करने की अनुमति दी है।

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

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

Main article: Constraint satisfaction problem

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

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

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

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

जबकि आमतौर पर बाधा संतुष्टि समस्या की उपरोक्त परिभाषा में शामिल नहीं किया जाता है, अंकगणितीय समीकरण और असमानताएं उनमें मौजूद चर के मूल्यों को बांधती हैं और इसलिए उन्हें बाधाओं का एक रूप माना जा सकता है। उनका डोमेन संख्याओं का समूह है (या तो पूर्णांक, तर्कसंगत, या वास्तविक), जो अनंत है: इसलिए, इन बाधाओं के संबंध भी अनंत हो सकते हैं; उदाहरण के लिए, $X=Y+1$ संतोषजनक मानों के युग्मों की अनंत संख्या है। अंकगणितीय समीकरणों और असमानताओं को अक्सर बाधा संतुष्टि समस्या की परिभाषा में नहीं माना जाता है, जो सीमित डोमेन तक सीमित है। हालाँकि इनका उपयोग अक्सर बाधा प्रोग्रामिंग में किया जाता है।

यह दिखाया जा सकता है कि फूटोशिकी या तंबाकू से होने वाली बीमारी (जिसे क्रॉस सम्स के रूप में भी जाना जाता है) जैसी कुछ प्रकार की परिमित तर्क पहेलियों में मौजूद अंकगणितीय असमानताओं या समीकरणों को गैर-अंकगणितीय बाधाओं के रूप में निपटाया जा सकता है (पैटर्न-आधारित बाधा संतुष्टि और तर्क पहेलियाँ देखें)).

समाधान

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

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

जटिलता

Main article: Complexity of constraint satisfaction

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

बाधा प्रोग्रामिंग

Main article: Constraint programming

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

बाधा तर्क प्रोग्रामिंग

Main article: Constraint logic programming

एक बाधा तर्क कार्यक्रम एक तर्क प्रोग्रामिंग है जिसमें खंडों के शरीर में बाधाएं शामिल होती हैं। उदाहरण के तौर पर, उपवाक्य A(X):-X>0,B(X) बाधा युक्त एक उपवाक्य है X>0 शरीर में। लक्ष्य में रुकावटें भी आ सकती हैं. लक्ष्य में बाधाएं और लक्ष्य को सिद्ध करने के लिए उपयोग किए जाने वाले खंडों को बाधा संग्रह नामक एक सेट में एकत्रित किया जाता है। इस सेट में वे बाधाएँ शामिल हैं जिन्हें दुभाषिया ने मूल्यांकन में आगे बढ़ने के लिए संतोषजनक माना है। परिणामस्वरूप, यदि यह सेट असंतोषजनक पाया जाता है, तो दुभाषिया पीछे हट जाता है। तर्क प्रोग्रामिंग में उपयोग किए जाने वाले शब्दों के समीकरणों को बाधाओं का एक विशेष रूप माना जाता है जिसे एकीकरण (कंप्यूटिंग) का उपयोग करके सरल बनाया जा सकता है। परिणामस्वरूप, बाधा भंडार को प्रतिस्थापन (तर्क) की अवधारणा का विस्तार माना जा सकता है जिसका उपयोग नियमित तर्क प्रोग्रामिंग में किया जाता है। बाधा तर्क प्रोग्रामिंग में उपयोग की जाने वाली सबसे आम प्रकार की बाधाएं पूर्णांक/तर्कसंगत/वास्तविक संख्याओं पर बाधाएं और परिमित डोमेन पर बाधाएं हैं।

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

बाधा संतुष्टि टूलकिट

बाधा संतुष्टि टूलकिट अनिवार्य प्रोग्रामिंग भाषाओं के लिए सॉफ्टवेयर लाइब्रेरी हैं जिनका उपयोग बाधा संतुष्टि समस्या को एन्कोड करने और हल करने के लिए किया जाता है।

• कैसोवरी बाधा सॉल्वर, बाधा संतुष्टि के लिए एक खुला स्रोत परियोजना (सी, जावा, पायथन और अन्य भाषाओं से सुलभ)।
• धूमकेतु (प्रोग्रामिंग भाषा), एक व्यावसायिक प्रोग्रामिंग भाषा और टूलकिट
• Gecode, C++ में लिखा गया एक खुला स्त्रोत पोर्टेबल टूलकिट, एक संपूर्ण सैद्धांतिक पृष्ठभूमि के उत्पादन-गुणवत्ता और अत्यधिक कुशल कार्यान्वयन के रूप में विकसित किया गया है।
• जेलिस्प, गेकोड से लिस्प (प्रोग्रामिंग भाषा) का एक खुला स्रोत पोर्टेबल रैपर। http://gelisp.sourceforge.net/
• IBM ILOG CP ऑप्टिमाइज़र: C++, Python, Java, .NET लाइब्रेरीज़ (मालिकाना, अकादमिक उपयोग के लिए निःशुल्क)। ILOG सॉल्वर/शेड्यूलर का उत्तराधिकारी, जिसे 2006 तक वाणिज्यिक बाधा प्रोग्रामिंग सॉफ़्टवेयर में बाज़ार का अग्रणी माना जाता था
• JaCoP (सॉल्वर), एक खुला स्रोत जावा बाधा सॉल्वर।
• OptaPlanner, एक अन्य खुला स्रोत जावा बाधा सॉल्वर।
• कोलोग , एक वाणिज्यिक जावा-आधारित बाधा सॉल्वर।
• लॉजिलाब-बाधा, बाधा प्रसार एल्गोरिदम के साथ शुद्ध पायथन में लिखा गया एक खुला स्रोत बाधा सॉल्वर।
• मिनियन (सॉल्वर), मॉडल/समस्याओं को निर्दिष्ट करने के उद्देश्य से एक छोटी भाषा के साथ C++ में लिखा गया एक ओपन-सोर्स बाधा सॉल्वर है।
• ZDC, बाधा संतुष्टि समस्याओं के मॉडलिंग और समाधान के लिए कंप्यूटर-एडेड बाधा संतुष्टि परियोजना में विकसित एक खुला स्रोत कार्यक्रम है।

अन्य बाधा प्रोग्रामिंग भाषाएँ

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

कार्यात्मक प्रोग्रामिंग में बाधाएं भी शामिल की गई हैं।

यह भी देखें

• बाधा संतुष्टि समस्या
• बाधा (गणित)
• उम्मीदवार समाधान
• बूलियन संतुष्टि समस्या
• निर्णय सिद्धांत
• संतुष्टि मॉड्यूलो सिद्धांत
• ज्ञान-आधारित विन्यास

संदर्भ

• Apt, Krzysztof (2003). Principles of constraint programming. Cambridge University Press. ISBN 978-0-521-82583-2.
• Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 978-1-55860-890-0.
• Dincbas, M.; Simonis, H.; Van Hentenryck, P. (1990). "Solving Large Combinatorial Problems in Logic Programming". Journal of Logic Programming. 8 (1–2): 75–93. doi:10.1016/0743-1066(90)90052-7.
• Freuder, Eugene; Mackworth, Alan, eds. (1994). Constraint-based reasoning. MIT Press. ISBN 978-0-262-56075-7.
• Frühwirth, Thom; Slim Abdennadher (2003). Essentials of constraint programming. Springer. ISBN 978-3-540-67623-2.
• Guesguen, Hans; Hertzberg Joachim (1992). A Perspective of Constraint Based Reasoning. Springer. ISBN 978-3-540-55510-0.
• Jaffar, Joxan; Michael J. Maher (1994). "Constraint logic programming: a survey". Journal of Logic Programming. 19/20: 503–581. doi:10.1016/0743-1066(94)90033-7.
• Laurière, Jean-Louis (1978). "A Language and a Program for Stating and Solving Combinatorial Problems". Artificial Intelligence. 10 (1): 29–127. doi:10.1016/0004-3702(78)90029-2.
• Lecoutre, Christophe (2009). Constraint Networks: Techniques and Algorithms. ISTE/Wiley. ISBN 978-1-84821-106-3.
• Marriott, Kim; Peter J. Stuckey (1998). Programming with constraints: An introduction. MIT Press. ISBN 978-0-262-13341-8.
• Rossi, Francesca; Peter van Beek; Toby Walsh, eds. (2006). Handbook of Constraint Programming. Elsevier. ISBN 978-0-444-52726-4. Archived from the original on 2012-10-04. Retrieved 2006-10-13.
• Tsang, Edward (1993). Foundations of Constraint Satisfaction. Academic Press. ISBN 978-0-12-701610-8.
• Van Hentenryck, Pascal (1989). Constraint Satisfaction in Logic Programming. MIT Press. ISBN 978-0-262-08181-8.
• Rashidi, Hassan.; Tsang, Edward. (2012). "Novel constraints satisfaction models for optimization problems in container terminals". Journal of Applied Mathematical Modelling. 37 (6): 3601–34. doi:10.1016/j.apm.2012.07.042.

बाहरी संबंध

• CSP Tutorial

वीडियो

• डॉ. मधु शर्मा द्वारा बाधा संतुष्टि व्याख्यान (3:47)
• एडवर्ड त्सांग द्वारा बाधा संतुष्टि समस्याओं का परिचय (7:34)
• बाधा संतुष्टि समस्याएं व्हीलर रूमल द्वारा (9:18)
• प्रौद्योगिकी संस्थान मद्रास द्वारा बाधा संतुष्टि समस्याओं पर एक व्याख्यान (51:59)
• सीएसपी पर व्याख्यान (1:16:39)
• बाधा संतुष्टि समस्याओं पर बर्कले एआई द्वारा व्याख्यान (1:17:38)
• एआई 5 में ग्रेजुएट कोर्स: प्रोफेसर मौसम द्वारा बाधा संतुष्टि (1:34:29)

श्रेणी:बाधा प्रोग्रामिंग|*