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

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

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

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

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

कांस्ट्रेन्ट सटिस्फैक्शन समस्या

Main article: कांस्ट्रेन्ट सटिस्फैक्शन समस्या

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

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

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

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

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

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

समाधान

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

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

काम्प्लेक्स

Main article: कांस्ट्रेन्ट सटिस्फैक्शन काम्प्लेक्स

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

कांस्ट्रेन्ट प्रोग्रामिंग

Main article: कांस्ट्रेन्ट प्रोग्रामिंग

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

कांस्ट्रेन्ट तर्क प्रोग्रामिंग

Main article: कांस्ट्रेन्ट तर्क प्रोग्रामिंग

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

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

कांस्ट्रेन्ट सटिस्फैक्शन टूलकिट

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

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