कन्सट्रैन्ट सटिस्फैक्शन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(7 intermediate revisions by 3 users not shown)
Line 1: Line 1:
कृत्रिम बुद्धिमत्ता और संचालन अनुसंधान में, बाधा [[संतुष्टि]] समाधान खोजने की प्रक्रिया है
आर्टिफीसियल इंटेलिजेंस और संचालन अनुसंधान में, '''कन्सट्रैन्ट सटिस्फैक्शन'''  समाधान खोजने की प्रक्रिया है इस प्रकार [[बाधा (गणित)|कांस्ट्रेन्ट (गणित)]] का सेट जो ऐसी स्थितियाँ लगाता है कि [[चर (गणित)|वैरीएबल (गणित)]] को सटिस्फैक्शन होना चाहिए।<ref name="Tsang2014">{{cite book|first=Edward|last=Tsang|title=Foundations of Constraint Satisfaction: The Classic Text|url=https://books.google.com/books?id=UFmRAwAAQBAJ|date=13 May 2014|publisher=BoD – Books on Demand|isbn=978-3-7357-2366-6}}</ref> इसलिए समाधान वैरीएबल के लिए मानो का सेट है जो सभी कांस्ट्रेन्ट को संतुष्ट करता है - जो कि व्यवहार्य क्षेत्र में एक बिंदु है।
[[बाधा (गणित)]] का सेट जो ऐसी स्थितियाँ लगाता है कि [[चर (गणित)]] को संतोषजनक होना चाहिए।<ref name="Tsang2014">{{cite book|first=Edward|last=Tsang|title=Foundations of Constraint Satisfaction: The Classic Text|url=https://books.google.com/books?id=UFmRAwAAQBAJ|date=13 May 2014|publisher=BoD – Books on Demand|isbn=978-3-7357-2366-6}}</ref> इसलिए समाधान चर के लिए मूल्यों का सेट है जो सभी बाधाओं को संतुष्ट करता है - यानी, व्यवहार्य क्षेत्र में बिंदु।


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


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


1980 और 1990 के दशक के दौरान, [[प्रोग्रामिंग भाषा]] में बाधाओं को एम्बेड करने का विकास किया गया। [[बाधा प्रोग्रामिंग]] के लिए आंतरिक समर्थन के साथ स्पष्ट रूप से तैयार की गई पहली भाषा [[प्रोलॉग]] थी। तब से, बाधा-प्रोग्रामिंग लाइब्रेरी अन्य भाषाओं में उपलब्ध हो गई हैं, जैसे [[सी++]] या [[जावा (प्रोग्रामिंग भाषा)]] (उदाहरण के लिए, जावा के लिए चोको)<ref>Choco: An Open-Source java library for constraint programming. https://choco-solver.org  Accessed Dec 12, 2021.</ref>).
1980 और 1990 के दशक के समय, [[प्रोग्रामिंग भाषा|प्रोग्रामिंग लैंग्वेज]] में कांस्ट्रेन्ट को एम्बेड करने का विकास किया गया था। [[बाधा प्रोग्रामिंग|कांस्ट्रेन्ट प्रोग्रामिंग]] के लिए आंतरिक समर्थन के साथ स्पष्ट रूप से तैयार की गई पहली लैंग्वेज [[प्रोलॉग]] थी। तब से, कांस्ट्रेन्ट-प्रोग्रामिंग लाइब्रेरी अन्य लैंग्वेज में उपलब्ध हो गई हैं, जैसे [[सी++]] या [[जावा (प्रोग्रामिंग भाषा)|जावा (प्रोग्रामिंग लैंग्वेज)]] (उदाहरण के लिए, जावा के लिए चोको)<ref>Choco: An Open-Source java library for constraint programming. https://choco-solver.org  Accessed Dec 12, 2021.</ref>).


==बाधा संतुष्टि समस्या==
==कन्सट्रैन्ट सटिस्फैक्शन  समस्या==
{{main|Constraint satisfaction problem}}
{{main|कांस्ट्रेन्ट सटिस्फैक्शन समस्या}}


जैसा कि मूल रूप से कृत्रिम बुद्धिमत्ता में परिभाषित किया गया है, बाधाएँ उन संभावित मूल्यों की गणना करती हैं जो किसी दिए गए दुनिया में चर का सेट ले सकता है। संभावित दुनिया, चरों के मूल्यों का कुल समनुदेशन है जो यह दर्शाता है कि दुनिया (वास्तविक या काल्पनिक) कैसी हो सकती है।<ref>{{Cite web | url=https://artint.info/2e/html/ArtInt2e.Ch4.S1.SS1.html | title=4.1.1 Variables and Worlds‣ 4.1 Possible Worlds, Variables, and Constraints ‣ Chapter 4 Reasoning with Constraints ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition}}</ref> अनौपचारिक रूप से, परिमित डोमेन मनमाने तत्वों का सीमित सेट है। ऐसे डोमेन पर बाधा संतुष्टि समस्या में चर का सेट होता है जिसका मान केवल डोमेन से लिया जा सकता है, और बाधाओं का सेट होता है, प्रत्येक बाधा चर के समूह के लिए अनुमत मान निर्दिष्ट करती है। इस समस्या का समाधान उन चरों का मूल्यांकन है जो सभी बाधाओं को संतुष्ट करते हैं। दूसरे शब्दों में, समाधान प्रत्येक चर को इस तरह से मान निर्दिष्ट करने का तरीका है कि सभी बाधाएँ इन मानों से संतुष्ट हों।
जैसा कि मूल रूप से आर्टिफीसियल इंटेलिजेंस में परिभाषित किया गया है, कांस्ट्रेन्टएँ उन संभावित मानो की गणना करती हैं जो किसी दिए गए संसार में वैरीएबल का सेट ले सकता है। संभावित संसार, वैरीएबलों के मानो का कुल असाइनमेंट है जो यह दर्शाता है कि संसार (वास्तविक या काल्पनिक) कैसी हो सकती है।<ref>{{Cite web | url=https://artint.info/2e/html/ArtInt2e.Ch4.S1.SS1.html | title=4.1.1 Variables and Worlds‣ 4.1 Possible Worlds, Variables, and Constraints ‣ Chapter 4 Reasoning with Constraints ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition}}</ref> अनौपचारिक रूप से, परिमित डोमेन अनैतिक कॉम्पोनेन्ट का सीमित सेट है। ऐसे डोमेन पर कन्सट्रैन्ट सटिस्फैक्शन  समस्या में वैरीएबल का सेट होता है जिसका मान केवल डोमेन से लिया जा सकता है, और कांस्ट्रेन्ट का सेट होता है, प्रत्येक कांस्ट्रेन्ट वैरीएबल के समूह के लिए अनुमत मान निर्दिष्ट करती है। इस प्रकार इस समस्या का समाधान उन वैरीएबलों का मूल्यांकन है जो सभी कांस्ट्रेन्ट को संतुष्ट करते हैं। दूसरे शब्दों में, समाधान प्रत्येक वैरीएबल को इस तरह से मान निर्दिष्ट करने का विधि है कि सभी कांस्ट्रेन्टएँ इन मानों से संतुष्ट होंता है।


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


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


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


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


यह दिखाया जा सकता है कि [[फूटोशिकी]] या [[ तंबाकू से होने वाली बीमारी |तंबाकू से होने वाली बीमारी]] (जिसे क्रॉस सम्स के रूप में भी जाना जाता है) जैसी कुछ प्रकार की परिमित तर्क पहेलियों में मौजूद अंकगणितीय असमानताओं या समीकरणों को गैर-अंकगणितीय बाधाओं के रूप में निपटाया जा सकता है (पैटर्न-आधारित बाधा संतुष्टि और तर्क पहेलियाँ देखें)<ref name="Pattern-Based Constraint Satisfaction and Logic Puzzles">{{in lang|en}} {{cite news | first = Denis | last = Berthier | title = Pattern-Based Constraint Satisfaction and Logic Puzzles | url = http://www.carva.org/denis.berthier/PBCS | archive-url = https://archive.today/20130112121944/http://www.carva.org/denis.berthier/PBCS | url-status = dead | archive-date = 12 January 2013 | work = Lulu Publishers | isbn = 978-1-291-20339-4 | date = 20 November 2012 | accessdate = 24 October 2012 }}</ref>).
यह दिखाया जा सकता है कि [[फूटोशिकी]] या [[ तंबाकू से होने वाली बीमारी |काकुरो]] (जिसे क्रॉस सम्स के रूप में भी जाना जाता है) जैसी कुछ प्रकार की परिमित तर्क पहेलियों में उपस्थित अंकगणितीय असमानताओं या समीकरणों को गैर-अंकगणितीय कांस्ट्रेन्ट के रूप में निपटाया जा सकता है (पैटर्न-आधारित कन्सट्रैन्ट सटिस्फैक्शन  और तर्क पहेलियाँ देखें)<ref name="Pattern-Based Constraint Satisfaction and Logic Puzzles">{{in lang|en}} {{cite news | first = Denis | last = Berthier | title = Pattern-Based Constraint Satisfaction and Logic Puzzles | url = http://www.carva.org/denis.berthier/PBCS | archive-url = https://archive.today/20130112121944/http://www.carva.org/denis.berthier/PBCS | url-status = dead | archive-date = 12 January 2013 | work = Lulu Publishers | isbn = 978-1-291-20339-4 | date = 20 November 2012 | accessdate = 24 October 2012 }}</ref>).


===समाधान===
===समाधान===


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


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


===जटिलता===
===काम्प्लेक्स===
{{main|Complexity of constraint satisfaction}}
{{main|कांस्ट्रेन्ट सटिस्फैक्शन काम्प्लेक्स}}


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


==बाधा प्रोग्रामिंग==
==कांस्ट्रेन्ट प्रोग्रामिंग==
{{main|Constraint programming}}
{{main|कांस्ट्रेन्ट प्रोग्रामिंग}}


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


===बाधा तर्क प्रोग्रामिंग===
===कांस्ट्रेन्ट तर्क प्रोग्रामिंग===
{{main|Constraint logic programming}}
{{main|कांस्ट्रेन्ट तर्क प्रोग्रामिंग}}


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


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


===बाधा संतुष्टि टूलकिट===
===कन्सट्रैन्ट सटिस्फैक्शन  टूलकिट===


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


* [[कैसोवरी बाधा सॉल्वर]], बाधा संतुष्टि के लिए खुला स्रोत परियोजना (सी, जावा, पायथन और अन्य भाषाओं से सुलभ)।
* [[कैसोवरी बाधा सॉल्वर|कैसोवरी कांस्ट्रेन्ट सॉल्वर]], कन्सट्रैन्ट सटिस्फैक्शन  के लिए ओपन सोर्स परियोजना (सी, जावा, पायथन और अन्य लैंग्वेज से सरल)।
* [[धूमकेतु (प्रोग्रामिंग भाषा)]], व्यावसायिक प्रोग्रामिंग भाषा और टूलकिट
* [[धूमकेतु (प्रोग्रामिंग भाषा)|कोमेट (प्रोग्रामिंग लैंग्वेज)]], व्यावसायिक प्रोग्रामिंग लैंग्वेज और टूलकिट
* [[Gecode]], C++ में लिखा गया [[ खुला स्त्रोत |खुला स्त्रोत]] पोर्टेबल टूलकिट, संपूर्ण सैद्धांतिक पृष्ठभूमि के उत्पादन-गुणवत्ता और अत्यधिक कुशल कार्यान्वयन के रूप में विकसित किया गया है।
* [[Gecode|गेकोड]], C++ में लिखा गया [[ खुला स्त्रोत |ओपन स्त्रोत]] पोर्टेबल टूलकिट, संपूर्ण सैद्धांतिक पृष्ठभूमि के उत्पादन-गुणवत्ता और अत्यधिक कुशल कार्यान्वयन के रूप में विकसित किया गया है।
* [[जेलिस्प]], गेकोड से [[लिस्प (प्रोग्रामिंग भाषा)]] का खुला स्रोत पोर्टेबल रैपर।<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> http://gelisp.sourceforge.net/
* [[जेलिस्प]], गेकोड से [[लिस्प (प्रोग्रामिंग भाषा)|लिस्प (प्रोग्रामिंग लैंग्वेज)]] का ओपन सोर्स पोर्टेबल रैपर <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> http://gelisp.sourceforge.net/
* [[IBM]] [[ILOG]] [http://www.ibm.com/analytics/cplex-cp-optimizer CP ऑप्टिमाइज़र]: C++, [https://pypi.python.org/pypi/docplex Python], Java, .NET लाइब्रेरीज़ (मालिकाना, [https://ibm.biz/COS_Faculty अकादमिक उपयोग के लिए निःशुल्क])।<ref name="CPOptimizer2018">{{cite journal|vauthors=Laborie P, Rogerie J, Shaw P, Vilim P|date=2018|title=शेड्यूलिंग के लिए IBM ILOG CP ऑप्टिमाइज़र|journal=Constraints|volume=23|issue=2|pages=210–250|doi=10.1007/s10601-018-9281-x|s2cid=4360357}}</ref> ILOG सॉल्वर/शेड्यूलर का उत्तराधिकारी, जिसे 2006 तक वाणिज्यिक बाधा प्रोग्रामिंग सॉफ़्टवेयर में बाज़ार का अग्रणी माना जाता था<ref name="RossiBeek2006">{{cite book|first1=Francesca|last1=Rossi|author1-link=Francesca Rossi|author2=Peter Van Beek|author3=Toby Walsh|title=बाधा प्रोग्रामिंग की हैंडबुक|url=https://books.google.com/books?id=Kjap9ZWcKOoC&pg=PA157|year=2006|publisher=Elsevier|isbn=978-0-444-52726-4|page=157}}</ref>
* [[IBM|आईबीएम आईएलओजी]] [http://www.ibm.com/analytics/cplex-cp-optimizer CP ऑप्टिमाइज़र]: C++, [https://pypi.python.org/pypi/docplex Python], Java, .NET लाइब्रेरीज़ (प्रोपर्टी, [https://ibm.biz/COS_Faculty अकादमिक उपयोग के लिए निःशुल्क])।<ref name="CPOptimizer2018">{{cite journal|vauthors=Laborie P, Rogerie J, Shaw P, Vilim P|date=2018|title=शेड्यूलिंग के लिए IBM ILOG CP ऑप्टिमाइज़र|journal=Constraints|volume=23|issue=2|pages=210–250|doi=10.1007/s10601-018-9281-x|s2cid=4360357}}</ref> ILOG सॉल्वर/शेड्यूलर का उत्तराधिकारी, जिसे 2006 तक वाणिज्यिक कांस्ट्रेन्ट प्रोग्रामिंग सॉफ़्टवेयर में मार्केट का अग्रणी माना जाता था <ref name="RossiBeek2006">{{cite book|first1=Francesca|last1=Rossi|author1-link=Francesca Rossi|author2=Peter Van Beek|author3=Toby Walsh|title=बाधा प्रोग्रामिंग की हैंडबुक|url=https://books.google.com/books?id=Kjap9ZWcKOoC&pg=PA157|year=2006|publisher=Elsevier|isbn=978-0-444-52726-4|page=157}}</ref>
* [[JaCoP (सॉल्वर)]], खुला स्रोत जावा बाधा सॉल्वर।
* [[JaCoP (सॉल्वर)|जेकॉप (सॉल्वर)]], ओपन सोर्स जावा कांस्ट्रेन्ट सॉल्वर।
* [[OptaPlanner]], अन्य खुला स्रोत जावा बाधा सॉल्वर।
* [[OptaPlanner|ऑप्टाप्लानर]], अन्य ओपन सोर्स जावा कांस्ट्रेन्ट सॉल्वर।
* [[ कोलोग ]], वाणिज्यिक जावा-आधारित बाधा सॉल्वर।
* [[ कोलोग ]], वाणिज्यिक जावा-आधारित कांस्ट्रेन्ट सॉल्वर।
* लॉजिलाब-बाधा, बाधा प्रसार एल्गोरिदम के साथ शुद्ध पायथन में लिखा गया खुला स्रोत बाधा सॉल्वर।
* लॉजिलाब-कांस्ट्रेन्ट, कांस्ट्रेन्ट प्रसार एल्गोरिदम के साथ शुद्ध पायथन में लिखा गया ओपन सोर्स कांस्ट्रेन्ट सॉल्वर।
* [[मिनियन (सॉल्वर)]], मॉडल/समस्याओं को निर्दिष्ट करने के उद्देश्य से छोटी भाषा के साथ C++ में लिखा गया ओपन-सोर्स बाधा सॉल्वर है।
* [[मिनियन (सॉल्वर)]], मॉडल/समस्याओं को निर्दिष्ट करने के उद्देश्य से छोटी लैंग्वेज के साथ C++ में लिखा गया ओपन-सोर्स कांस्ट्रेन्ट सॉल्वर है।
* ZDC, बाधा संतुष्टि समस्याओं के मॉडलिंग और समाधान के लिए कंप्यूटर-एडेड बाधा संतुष्टि परियोजना में विकसित खुला स्रोत कार्यक्रम है।
* जेडडीसी, कन्सट्रैन्ट सटिस्फैक्शन  समस्याओं के मॉडलिंग और समाधान के लिए कंप्यूटर-एडेड कन्सट्रैन्ट सटिस्फैक्शन  परियोजना में विकसित ओपन सोर्स प्रोग्राम है।


===अन्य बाधा प्रोग्रामिंग भाषाएँ===
===अन्य कांस्ट्रेन्ट प्रोग्रामिंग लैंग्वेज===


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


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


== यह भी देखें ==
== यह भी देखें ==


*बाधा संतुष्टि समस्या
*कन्सट्रैन्ट सटिस्फैक्शन  समस्या
* बाधा (गणित)
* कांस्ट्रेन्ट (गणित)
*[[उम्मीदवार समाधान]]
*[[उम्मीदवार समाधान|अभ्यर्थी समाधान]]
* बूलियन संतुष्टि समस्या
* बूलियन सटिस्फैक्शन समस्या
* [[निर्णय सिद्धांत]]
* [[निर्णय सिद्धांत]]
* [[संतुष्टि मॉड्यूलो सिद्धांत]]
* [[संतुष्टि मॉड्यूलो सिद्धांत|सटिस्फैक्शन मॉड्यूलो सिद्धांत]]
* ज्ञान-आधारित विन्यास
* ज्ञान-आधारित विन्यास


Line 218: Line 217:
}}
}}
{{Refend}}
{{Refend}}
 
==बाहरी संबंध                                                                                                                             ==
 
==बाहरी संबंध==
*[https://web.archive.org/web/20090211163302/http://4c.ucc.ie/web/outreach/tutorial.html CSP Tutorial]
*[https://web.archive.org/web/20090211163302/http://4c.ucc.ie/web/outreach/tutorial.html CSP Tutorial]
===वीडियो===
===वीडियो===
*[https://www.youtube.com/watch?v=J4xMBJNy41w डॉ. मधु शर्मा द्वारा बाधा संतुष्टि व्याख्यान (3:47)]
*[https://www.youtube.com/watch?v=J4xMBJNy41w डॉ. मधु शर्मा द्वारा कन्सट्रैन्ट सटिस्फैक्शन  व्याख्यान (3:47)]
*[https://www.youtube.com/watch?v=wrs6Lvo5LZM एडवर्ड त्सांग द्वारा बाधा संतुष्टि समस्याओं का परिचय (7:34)]
*[https://www.youtube.com/watch?v=wrs6Lvo5LZM एडवर्ड त्सांग द्वारा कन्सट्रैन्ट सटिस्फैक्शन  समस्याओं का परिचय (7:34)]
*[https://www.youtube.com/watch?v=UhAmM3z6KS0 बाधा संतुष्टि समस्याएं व्हीलर रूमल द्वारा (9:18)]
*[https://www.youtube.com/watch?v=UhAmM3z6KS0 कन्सट्रैन्ट सटिस्फैक्शन  समस्याएं व्हीलर रूमल द्वारा (9:18)]
*[https://www.youtube.com/watch?v=il20Q5tXp-भारतीय प्रौद्योगिकी संस्थान मद्रास द्वारा बाधा संतुष्टि समस्याओं पर व्याख्यान (51:59)]
*[https://www.youtube.com/watch?v=il20Q5tXp-भारतीय प्रौद्योगिकी संस्थान मद्रास द्वारा कन्सट्रैन्ट सटिस्फैक्शन  समस्याओं पर व्याख्यान (51:59)]
*[https://www.youtube.com/watch?v=hJ9WOiueJes सीएसपी पर व्याख्यान (1:16:39)]
*[https://www.youtube.com/watch?v=hJ9WOiueJes सीएसपी पर व्याख्यान (1:16:39)]
*[https://www.youtube.com/watch?v=595zA9OXCns बाधा संतुष्टि समस्याओं पर बर्कले एआई द्वारा व्याख्यान (1:17:38)]
*[https://www.youtube.com/watch?v=595zA9OXCns कन्सट्रैन्ट सटिस्फैक्शन  समस्याओं पर बर्कले एआई द्वारा व्याख्यान (1:17:38)]
*[https://www.youtube.com/watch?v=il20Q5tXp-A एआई 5 में ग्रेजुएट कोर्स: प्रोफेसर मौसम द्वारा बाधा संतुष्टि (1:34:29)]
*[https://www.youtube.com/watch?v=il20Q5tXp-A एआई 5 में ग्रेजुएट कोर्स: प्रोफेसर मौसम द्वारा कन्सट्रैन्ट सटिस्फैक्शन  (1:34:29)]


{{Major subfields of optimization}}
[[Category:Articles with English-language sources (en)]]
[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:CS1]]
[[Category:Created On 24/07/2023]]
[[Category:Created On 24/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]

Latest revision as of 11:20, 12 August 2023

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

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

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

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

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

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

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

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

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

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

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

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

समाधान

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

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

काम्प्लेक्स

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

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

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

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

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

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

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

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

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

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

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

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

अन्य कांस्ट्रेन्ट प्रोग्रामिंग लैंग्वेज

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

कार्यात्मक प्रोग्रामिंग में कांस्ट्रेन्ट भी सम्मिलित की गई हैं।

यह भी देखें

संदर्भ

  1. ↑ Tsang, Edward (13 May 2014). Foundations of Constraint Satisfaction: The Classic Text. BoD – Books on Demand. ISBN 978-3-7357-2366-6.
  2. ↑ Choco: An Open-Source java library for constraint programming. https://choco-solver.org Accessed Dec 12, 2021.
  3. ↑ "4.1.1 Variables and Worlds‣ 4.1 Possible Worlds, Variables, and Constraints ‣ Chapter 4 Reasoning with Constraints ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition".
  4. ↑ (in English) Berthier, Denis (20 November 2012). "Pattern-Based Constraint Satisfaction and Logic Puzzles". Lulu Publishers. ISBN 978-1-291-20339-4. Archived from the original on 12 January 2013. Retrieved 24 October 2012.
  5. ↑ 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.
  6. ↑ Laborie P, Rogerie J, Shaw P, Vilim P (2018). "शेड्यूलिंग के लिए IBM ILOG CP ऑप्टिमाइज़र". Constraints. 23 (2): 210–250. doi:10.1007/s10601-018-9281-x. S2CID 4360357.
  7. ↑ Rossi, Francesca; Peter Van Beek; Toby Walsh (2006). बाधा प्रोग्रामिंग की हैंडबुक. Elsevier. p. 157. ISBN 978-0-444-52726-4.

बाहरी संबंध

वीडियो

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=कन्सट्रैन्ट_सटिस्फैक्शन&oldid=245142’