काँस्ट्रैंट प्रोग्रामिंग: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(8 intermediate revisions by 6 users not shown)
Line 1: Line 1:
{{Programming paradigms}}
'''काँस्ट्रैंट प्रोग्रामिंग''' (Constraint programming) (सीपी)<ref name=":0">{{Cite book|url=https://books.google.com/books?id=Kjap9ZWcKOoC&q=handbook+of+constraint+programming&pg=PP1|title=Handbook of Constraint Programming|last1=Rossi|first1=Francesca|last2=Beek|first2=Peter van|last3=Walsh|first3=Toby|date=2006-08-18|publisher=Elsevier|isbn=9780080463803|language=en}}</ref> की [[मिश्रित]] समस्याओं को हल करने के लिए प्रतिमान का उपयोग करते हैं जो कृत्रिम बुद्धि, [[कंप्यूटर विज्ञान]] और संचालन अनुसंधान से तकनीकों की विस्तृत श्रृंखला पर आधारित है। काँस्ट्रैंट प्रोग्रामिंग में, उपयोगकर्ता घोषणात्मक रूप से निर्णय चर के समुच्चय के लिए व्यवहार्य समाधान पर [[बाधा (गणित)|काँस्ट्रैंट (गणित)]] बताते हैं। काँस्ट्रैंटएँ [[अनिवार्य प्रोग्रामिंग]] भाषाओं की सामान्य [[भाषा आदिम|प्राचीन भाषा]] से भिन्न होती हैं, जिसमें वे निष्पादित करने के लिए चरणों का चरण या अनुक्रम निर्दिष्ट नहीं करते हैं, जिसके अतिरिक्त इसके समाधान के गुण पाए जाते हैं। काँस्ट्रैंटओं के अतिरिक्त, उपयोगकर्ताओं को इन काँस्ट्रैंटओं को हल करने के लिए विधि भी निर्दिष्ट करने की आवश्यकता होती है। यह सामान्यतः कालानुक्रमिक [[बैक ट्रैकिंग]] और [[बाधा प्रसार|काँस्ट्रैंट प्रसार]] जैसे मानक तरीकों पर आधारित होता है, किन्तु समस्या-विशिष्ट ब्रांचिंग ह्यूरिस्टिक (कंप्यूटर विज्ञान) जैसे अनुकूलित कोड का उपयोग करता हैं।
बाधा प्रोग्रामिंग (सीपी)<ref name=":0">{{Cite book|url=https://books.google.com/books?id=Kjap9ZWcKOoC&q=handbook+of+constraint+programming&pg=PP1|title=Handbook of Constraint Programming|last1=Rossi|first1=Francesca|last2=Beek|first2=Peter van|last3=Walsh|first3=Toby|date=2006-08-18|publisher=Elsevier|isbn=9780080463803|language=en}}</ref> [[मिश्रित]] समस्याओं को हल करने के लिए प्रतिमान है जो कृत्रिम बुद्धि, [[कंप्यूटर विज्ञान]] और संचालन अनुसंधान से तकनीकों की विस्तृत श्रृंखला पर आधारित है। बाधा प्रोग्रामिंग में, उपयोगकर्ता घोषणात्मक रूप से निर्णय चर के सेट के लिए व्यवहार्य समाधान पर [[बाधा (गणित)]] बताते हैं। बाधाएँ [[अनिवार्य प्रोग्रामिंग]] भाषाओं की सामान्य [[भाषा आदिम]] से भिन्न होती हैं, जिसमें वे निष्पादित करने के लिए चरणों का चरण या अनुक्रम निर्दिष्ट नहीं करते हैं, बल्कि समाधान के गुण पाए जाते हैं। बाधाओं के अतिरिक्त, उपयोगकर्ताओं को इन बाधाओं को हल करने के लिए विधि भी निर्दिष्ट करने की आवश्यकता होती है। यह सामान्यतः कालानुक्रमिक [[बैक ट्रैकिंग]] और [[बाधा प्रसार]] जैसे मानक तरीकों पर आधारित होता है, किन्तु समस्या-विशिष्ट ब्रांचिंग ह्यूरिस्टिक (कंप्यूटर विज्ञान) जैसे अनुकूलित कोड का उपयोग कर सकता है।


बाधा प्रोग्रामिंग इसकी जड़ लेती है और [[बाधा तर्क प्रोग्रामिंग]] के रूप में व्यक्त की जा सकती है, जो [[तर्क कार्यक्रम]] में बाधाओं को एम्बेड करती है। लॉजिक प्रोग्रामिंग का यह संस्करण जाफ़र और लासेज़ के कारण है,<ref>Jaffar, Joxan, and J-L. Lassez. "[https://dl.acm.org/citation.cfm?id=41635 Constraint logic programming]." Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. ACM, 1987.</ref> जिन्होंने 1987 में बाधाओं के विशिष्ट वर्ग का विस्तार किया जिसे [[प्रस्तावना द्वितीय]] में प्रस्तुत किया गया था। बाधा तर्क प्रोग्रामिंग के पहले कार्यान्वयन [[प्रोलॉग III]], [[सीएलपी (आर)]], और सीएचआईपी (प्रोग्रामिंग भाषा) थे।
काँस्ट्रैंट प्रोग्रामिंग इसकी जड़ लेती है और [[बाधा तर्क प्रोग्रामिंग|काँस्ट्रैंट लॉजिकल प्रोग्रामिंग]] के रूप में व्यक्त की जाती हैं, जो लॉजिकल फंक्शन में काँस्ट्रैंटओं को एम्बेड करती है। लॉजिकल प्रोग्रामिंग का यह संस्करण जाफ़र और लासेज़ के कारण उत्कृष्ट किया गया है,<ref>Jaffar, Joxan, and J-L. Lassez. "[https://dl.acm.org/citation.cfm?id=41635 Constraint logic programming]." Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. ACM, 1987.</ref> जिन्होंने 1987 में काँस्ट्रैंटओं के विशिष्ट वर्ग का विस्तार किया जिसे [[प्रस्तावना द्वितीय]] में प्रस्तुत किया गया था। काँस्ट्रैंट लॉजिकल प्रोग्रामिंग के पहले कार्यान्वयन [[प्रोलॉग III]], [[सीएलपी (आर)]], और सीएचआईपी (प्रोग्रामिंग भाषा) थे।


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


== बाधा तर्क प्रोग्रामिंग ==
== काँस्ट्रैंट लॉजिकल प्रोग्रामिंग ==
{{main|Constraint logic programming}}
{{main|बाधा तार्किक प्रोग्रामिंग}}
बाधा प्रोग्रामिंग मेजबान भाषा में बाधाओं का एम्बेडिंग है। उपयोग की जाने वाली पहली होस्ट भाषाएं लॉजिक प्रोग्रामिंग भाषाएं थीं, इसलिए इस क्षेत्र को प्रारंभ में कंस्ट्रेंट लॉजिक प्रोग्रामिंग कहा जाता था। दो प्रतिमान तार्किक चर और बैकट्रैकिंग जैसी कई महत्वपूर्ण विशेषताओं को साझा करते हैं। आज अधिकांश [[प्रोलॉग]] कार्यान्वयन में बाधा [[तर्क प्रोग्रामिंग]] के लिए या से अधिक पुस्तकालय सम्मलित हैं।


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


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


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


== बाधा संतुष्टि समस्या ==
टेम्पोरल समवर्ती काँस्ट्रैंट प्रोग्रामिंग (TCC) और गैर-नियतात्मक लौकिक समवर्ती काँस्ट्रैंट प्रोग्रामिंग (MJV) काँस्ट्रैंट प्रोग्रामिंग के प्रकार हैं जो समय के साथ निपट सकते हैं।
{{main|Constraint satisfaction problem}}
 
एक बाधा कई चर के बीच संबंध है जो उन मूल्यों को सीमित करता है जो ये चर साथ ले सकते हैं।
== काँस्ट्रैंट संतुष्टि समस्या ==
{{main|बाधा संतुष्टि समस्या}}
एक काँस्ट्रैंट कई चर के बीच संबंध है जो उन मूल्यों को सीमित करता है जो ये चर साथ ले सकते हैं।
{{math theorem
{{math theorem
|Definition
|परिभाषा
|A constraint satisfaction problem on finite domains (or CSP) is defined by a triplet <math>(\mathcal{X},\mathcal{D},\mathcal{C})</math> where:
|परिमित डोमेन (या सीएसपी) पर एक बाधा संतुष्टि समस्या को ट्रिपलेट द्वारा परिभाषित किया गया है <math>(\mathcal{X},\mathcal{D},\mathcal{C})</math> जहाँ:
* <math>\mathcal{X} = \{x_1, \dots, x_n \}</math> is the set of variables of the problem;
* <math>\mathcal{X} = \{x_1, \dots, x_n \}</math> समस्या के चरों का समुच्चय है;
* <math>\mathcal{D} = \{\mathcal{D}_1, \dots, \mathcal{D}_n \}</math> is the set of domains of the variables, i.e., for all <math>k \in [1; n]</math> we have <math>x_k \in \mathcal{D}_k</math>;
* <math>\mathcal{D} = \{\mathcal{D}_1, \dots, \mathcal{D}_n \}</math> चर के डोमेन का सेट है, यानी सभी के लिए <math>k \in [1; n]</math> हमारे पास <math>x_k \in \mathcal{D}_k</math>;
* <math>\mathcal{C} = \{C_1, \dots, C_m \}</math> is a set of constraints. A constraint <math>C_i=(\mathcal{X}_i, \mathcal{R}_i)</math> is defined by a set <math>\mathcal{X}_i = \{x_{i_1}, \dots, x_{i_k}\}</math> of variables and a relation <math>\mathcal{R}_i \subset \mathcal{D}_{i_1} \times \dots \times \mathcal{D}_{i_k}</math> which defines the set of values allowed simultaneously for the variables of <math>\mathcal{X}_i</math>:
* <math>\mathcal{C} = \{C_1, \dots, C_m \}</math> बाधाओं का एक समूह है। एक स्थिरांक <math>C_i=(\mathcal{X}_i, \mathcal{R}_i)</math> एक समुच्चय के रूप में दर्शाया जाता हैं <math>\mathcal{X}_i = \{x_{i_1}, \dots, x_{i_k}\}</math> चर और एक संबंध <math>\mathcal{R}_i \subset \mathcal{D}_{i_1} \times \dots \times \mathcal{D}_{i_k}</math> जो चर के लिए एक साथ अनुमत मानों के सेट को परिभाषित करता है <math>\mathcal{X}_i</math>:
}}
}}
बाधाओं की तीन श्रेणियां सम्मलित हैं:
काँस्ट्रैंटओं की तीन श्रेणियां सम्मलित हैं:
* विस्तृत बाधाएँ: बाधाओं को उन मूल्यों के समूह की गणना करके परिभाषित किया जाता है जो उन्हें संतुष्ट करेंगे;
* विस्तृत काँस्ट्रैंटएँ: काँस्ट्रैंटओं को उन मूल्यों के समूह की गणना करके परिभाषित किया जाता है जो उन्हें संतुष्ट करेंगे;
* अंकगणितीय बाधाएँ: बाधाओं को अंकगणितीय अभिव्यक्ति द्वारा परिभाषित किया जाता है, अर्थात, उपयोग करना <math><, >, \leq, \geq, =, \neq,...</math>;
* अंकगणितीय काँस्ट्रैंटएँ: काँस्ट्रैंटओं को अंकगणितीय अभिव्यक्ति द्वारा परिभाषित किया जाता है, अर्थात <math><, >, \leq, \geq, =, \neq,...</math> का उपयोग करना
* तार्किक बाधाएँ: बाधाओं को स्पष्ट शब्दार्थ के साथ परिभाषित किया गया है, अर्थात, AllDifferent, AtMost,...
* लॉजिकल काँस्ट्रैंटएँ: काँस्ट्रैंटओं को स्पष्ट शब्दार्थ के साथ परिभाषित किया गया है, अर्थात, सभी अलग, सबसे ज्यादा,...


{{math theorem
{{math theorem
|Definition
|परिभाषा
| An assignment (or model) <math>\mathcal{A}</math> of a CSP <math>P = (\mathcal{X},\mathcal{D},\mathcal{C})</math> is defined by the couple <math>\mathcal{A} = (\mathcal{X_{\mathcal{A}}}, \mathcal{V_{\mathcal{A}}})</math> जहां:
|एक असाइनमेंट (या मॉडल) <math>\mathcal{A}</math> एक सीएसपी का <math>P = (\mathcal{X},\mathcal{D},\mathcal{C})</math> युगल द्वारा परिभाषित किया गया है <math>\mathcal{A} = (\mathcal{X_{\mathcal{A}}}, \mathcal{V_{\mathcal{A}}})</math> जहां:
गणित> \mathcal{X_{\mathcal{A}}} \subset \mathcal{X} <nowiki></math></nowiki> चर का सबसेट है;
<math> \mathcal{X_{\mathcal{A}}} \subset \mathcal{X} <nowiki></math></nowiki> चर का सबसमुच्चय है;
गणित>\mathcal{V_{\mathcal{A}}} = \{v_{\mathcal{A}_1}, \dots, v_{\mathcal{A}_k}\} \in \{ \mathcal{D} _{\mathcal{A}_1}, \dots, \mathcal{D}_{\mathcal{A}_k}\}</math> असाइन किए गए वेरिएबल्स द्वारा लिए गए मानों का टपल है।
<math>\mathcal{V_{\mathcal{A}}} = \{v_{\mathcal{A}_1}, \dots, v_{\mathcal{A}_k}\} \in \{ \mathcal{D} _{\mathcal{A}_1}, \dots, \mathcal{D}_{\mathcal{A}_k}\}</math> असाइन किए गए वेरिएबल्स द्वारा लिए गए मानों का टपल है।
}}
}}


Assignment वेरिएबल का उसके डोमेन के मान से जुड़ाव है। आंशिक असाइनमेंट तब होता है जब समस्या के चर का सबसेट असाइन किया गया हो। कुल असाइनमेंट तब होता है जब समस्या के सभी चर असाइन किए गए हों।
एसाइमेंट वेरिएबल का उसके डोमेन के मान से जुड़ाव है। आंशिक असाइनमेंट तब होता है जब समस्या के चर का सबसमुच्चय असाइन किया गया हो। कुल असाइनमेंट तब होता है जब समस्या के सभी चर असाइन किए गए हों।


{{math theorem
{{math theorem
|Property
|Property
|Given <math>\mathcal{A} = (\mathcal{X_{\mathcal{A}}}, \mathcal{V_{\mathcal{A}}})</math> एक CSP का असाइनमेंट (आंशिक या कुल) गणित> पी = (\mathcal{X},\mathcal{D},\mathcal{C})</math>, और <math>C_i = (\mathcal{X}_i, \mathcal{R}_i)</math> की एक बाधा <math>P</math> जैसे कि <math>\mathcal{X}_i \subset \mathcal{X_{\mathcal{A}}}</math>, असाइनमेंट <math>\mathcal{A}</math> बाध्यता को संतुष्ट करता है <math>C_i</math> अगर और केवल अगर सभी मान <math>\mathcal{V}_{\mathcal{A}_i} = \{ v_i \in \mathcal{V}_{\mathcal{A}} \mbox{ tel que } x_i \in \mathcal{X}_{i} \}</math> बाधा के चर के <math>C_i</math> से संबंधित <math>\mathcal{R}_i</math>.
|Given <math>\mathcal{A} = (\mathcal{X_{\mathcal{A}}}, \mathcal{V_{\mathcal{A}}})</math> an assignation (partial or total) of a CSP <math>P = (\mathcal{X},\mathcal{D},\mathcal{C})</math>, and <math>C_i = (\mathcal{X}_i, \mathcal{R}_i)</math> a constraint of <math>P</math> such as <math>\mathcal{X}_i \subset \mathcal{X_{\mathcal{A}}}</math>, the assignation <math>\mathcal{A}</math> satisfies the constraint <math>C_i</math> if and only if all the values <math>\mathcal{V}_{\mathcal{A}_i} = \{ v_i \in \mathcal{V}_{\mathcal{A}} \mbox{ tel que } x_i \in \mathcal{X}_{i} \}</math> of the variables of the constraint <math>C_i</math> belongs to <math>\mathcal{R}_i</math>.
}}
}}


{{math theorem
{{math theorem
|Definition
|परिभाषा
|A solution of a CSP is a total assignation which satisfied all the constraints of the problem.}}
|सीएसपी का एक समाधान कुल असाइनमेंट है जो समस्या की सभी बाधाओं को संतुष्ट करता है।}}
सीएसपी के समाधान की खोज के समय, उपयोगकर्ता निम्नलिखित की इच्छा कर सकता है:
सीएसपी के समाधान की खोज के समय, उपयोगकर्ता निम्नलिखित की इच्छा कर सकता है:


* एक समाधान खोजना (सभी बाधाओं को पूरा करना);
* एक समाधान खोजना (सभी काँस्ट्रैंटओं को पूरा करना);
*समस्या के सभी समाधान खोजना;
*समस्या के सभी समाधान खोजना;
* समस्या की असंतोषजनकता को सिद्ध करना।
* समस्या की असंतोषजनकता को सिद्ध करना।


== बाधा अनुकूलन समस्या ==
== काँस्ट्रैंट अनुकूलन समस्या ==
{{Main|Constrained optimization}}
{{Main|विवश अनुकूलन}}
एक बाधा अनुकूलन समस्या (COP) वस्तुनिष्ठ कार्य से जुड़ी बाधा संतुष्टि समस्या है।
 
काँस्ट्रैंट अनुकूलन समस्या (COP) वस्तुनिष्ठ कार्य से जुड़ी काँस्ट्रैंट संतुष्टि समस्या है।


एक न्यूनीकरण (अधिकतमकरण) सीओपी का इष्टतम समाधान समाधान है जो उद्देश्य समारोह के मूल्य को कम करता है (अधिकतम करता है)।
न्यूनीकरण (अधिकतमकरण) सीओपी का इष्टतम समाधान समाधान है जो उद्देश्य समारोह के मूल्य को कम करता है (अधिकतम करता है)।


सीएसपी के समाधान की खोज के समय, उपयोगकर्ता निम्नलिखित की इच्छा कर सकता है:
सीएसपी के समाधान की खोज के समय, उपयोगकर्ता निम्नलिखित की इच्छा कर सकता है:


* एक समाधान खोजना (सभी बाधाओं को पूरा करना);
* समाधान खोजना (सभी काँस्ट्रैंटओं को पूरा करना);


* उद्देश्य के संबंध में सबसे अच्छा समाधान खोजना;
* उद्देश्य के संबंध में सबसे अच्छा समाधान खोजना;
Line 69: Line 70:
* समस्या की असंतोषजनकता को सिद्ध करना।
* समस्या की असंतोषजनकता को सिद्ध करना।


== गड़बड़ी बनाम शोधन मॉडल ==
== त्रुटि तथा शोधन मॉडल में अंतर ==
बाधा-आधारित प्रोग्रामिंग के लिए भाषाएँ दो दृष्टिकोणों में से का अनुसरण करती हैं:<ref>{{cite book |last1=Mayoh |first1=Brian |last2=Tyugu |first2=Enn |last3=Penjam |first3=Jaan |date=1993 |title=Constraint Programming |url=https://books.google.com/books?id=B0aqCAAAQBAJ |publisher=[[Springer Science+Business Media]] |page=76 |isbn=9783642859830}}</ref>
काँस्ट्रैंट-आधारित प्रोग्रामिंग के लिए भाषाएँ दो दृष्टिकोणों में से का अनुसरण करती हैं:<ref>{{cite book |last1=Mayoh |first1=Brian |last2=Tyugu |first2=Enn |last3=Penjam |first3=Jaan |date=1993 |title=Constraint Programming |url=https://books.google.com/books?id=B0aqCAAAQBAJ |publisher=[[Springer Science+Business Media]] |page=76 |isbn=9783642859830}}</ref>
* शोधन मॉडल: समस्या में वेरिएबल्स को प्रारंभ में असाइन नहीं किया गया है, और प्रत्येक वेरिएबल को अपनी सीमा या डोमेन में सम्मलित किसी भी मान को सम्मलित करने में सक्षम माना जाता है। जैसे-जैसे गणना आगे बढ़ती है, चर के डोमेन में मान काट दिए जाते हैं यदि उन्हें अन्य चर के संभावित मानों के साथ असंगत दिखाया जाता है, जब तक कि प्रत्येक चर के लिए मान नहीं मिल जाता।
* शोधन मॉडल: समस्या में वेरिएबल्स को प्रारंभ में असाइन नहीं किया गया है, और प्रत्येक वेरिएबल को अपनी सीमा या डोमेन में सम्मलित किसी भी मान को सम्मलित करने में सक्षम माना जाता है। जैसे-जैसे गणना आगे बढ़ती है, चर के डोमेन में मान काट दिए जाते हैं यदि उन्हें अन्य चर के संभावित मानों के साथ असंगत दिखाया जाता है, जब तक कि प्रत्येक चर के लिए मान नहीं मिल जाता।
* पर्टर्बेशन मॉडल: समस्या में वेरिएबल्स को प्रारंभिक मान दिया जाता है। अलग-अलग समय पर या से अधिक चर गड़बड़ी (उनके पुराने मूल्य में परिवर्तन) प्राप्त करते हैं, और सिस्टम गड़बड़ी के अनुरूप अन्य चर के लिए नए मान निर्दिष्ट करने की कोशिश कर रहे परिवर्तन को प्रचारित करता है।
* पर्टर्बेशन मॉडल: समस्या में वेरिएबल्स को प्रारंभिक मान दिया जाता है। अलग-अलग समय पर या से अधिक चर गड़बड़ी (उनके पुराने मूल्य में परिवर्तन) प्राप्त करते हैं, और सिस्टम गड़बड़ी के अनुरूप अन्य चर के लिए नए मान निर्दिष्ट करने की प्रयास कर रहे परिवर्तन को प्रचारित करता है।
बाधा संतुष्टि समस्याओं में बाधा प्रसार परिशोधन मॉडल का विशिष्ट उदाहरण है, और [[स्प्रेडशीट]] गड़बड़ी मॉडल का विशिष्ट उदाहरण है।
काँस्ट्रैंट संतुष्टि समस्याओं में काँस्ट्रैंट प्रसार परिशोधन मॉडल का विशिष्ट उदाहरण है, और [[स्प्रेडशीट]] गड़बड़ी मॉडल का विशिष्ट उदाहरण है।
 
परिशोधन मॉडल अधिक सामान्य है, क्योंकि यह चर को ही मान के लिए प्रतिबंधित नहीं करता है, इससे ही समस्या के कई समाधान हो सकते हैं। चूंकि, मिश्रित अनिवार्य बाधा वस्तु-उन्मुख भाषाओं का उपयोग करने वाले प्रोग्रामर के लिए गड़बड़ी मॉडल अधिक सहज है।<ref>Lopez, G., Freeman-Benson, B., & Borning, A. (1994, January). [ftp://trout.cs.washington.edu/tr/1993/09/UW-CSE-93-09-04.pdf Kaleidoscope: A constraint imperative programming language.] In ''Constraint Programming'' (pp. 313-329). Springer Berlin Heidelberg.</ref>
 


परिशोधन मॉडल अधिक सामान्य है, क्योंकि यह चर को ही मान के लिए प्रतिबंधित नहीं करता है, इससे ही समस्या के कई समाधान हो सकते हैं। चूंकि, मिश्रित अनिवार्य काँस्ट्रैंट वस्तु-उन्मुख भाषाओं का उपयोग करने वाले प्रोग्रामर के लिए गड़बड़ी मॉडल अधिक सहज है।<ref>Lopez, G., Freeman-Benson, B., & Borning, A. (1994, January). [ftp://trout.cs.washington.edu/tr/1993/09/UW-CSE-93-09-04.pdf Kaleidoscope: A constraint imperative programming language.] In ''Constraint Programming'' (pp. 313-329). Springer Berlin Heidelberg.</ref>
== डोमेन ==
== डोमेन ==
बाधा प्रोग्रामिंग में उपयोग की जाने वाली बाधाएँ सामान्यतः कुछ विशिष्ट डोमेन पर होती हैं। बाधा प्रोग्रामिंग के लिए कुछ लोकप्रिय डोमेन हैं:
'''काँस्ट्रैंट प्रोग्रामिंग''' में उपयोग की जाने वाली काँस्ट्रैंटएँ सामान्यतः कुछ विशिष्ट [[डोमेन]] पर होती हैं। काँस्ट्रैंट प्रोग्रामिंग के लिए कुछ लोकप्रिय डोमेन हैं:


* [[बूलियन डेटाटाइप]] डोमेन, जहां केवल सही/गलत प्रतिबंध लागू होते हैं ([[बूलियन संतुष्टि समस्या]])
* [[बूलियन डेटाटाइप]] डोमेन, जहां केवल सही/गलत प्रतिबंध लागू होते हैं ([[बूलियन संतुष्टि समस्या]])
Line 85: Line 84:
* अंतराल_ (गणित) डोमेन, विशेष रूप से शेड्यूलिंग समस्याओं के लिए
* अंतराल_ (गणित) डोमेन, विशेष रूप से शेड्यूलिंग समस्याओं के लिए
* रैखिक बीजगणित डोमेन, जहां केवल रैखिक कार्यों का वर्णन और विश्लेषण किया जाता है (चूंकि गैर-रैखिक समस्याओं के दृष्टिकोण सम्मलित हैं)
* रैखिक बीजगणित डोमेन, जहां केवल रैखिक कार्यों का वर्णन और विश्लेषण किया जाता है (चूंकि गैर-रैखिक समस्याओं के दृष्टिकोण सम्मलित हैं)
* विक्षनरी: परिमित डोमेन, जहां [[परिमित सेट]]ों पर बाधाओं को परिभाषित किया गया है
* विक्षनरी: परिमित डोमेन, जहां [[परिमित सेट|परिमित समुच्चयों]] पर काँस्ट्रैंटओं को परिभाषित किया गया है
* मिश्रित डोमेन, उपरोक्त में से दो या अधिक सम्मलित हैं
* मिश्रित डोमेन, उपरोक्त में से दो या अधिक सम्मलित हैं


परिमित डोमेन बाधा प्रोग्रामिंग के सबसे सफल डोमेन में से है। कुछ क्षेत्रों में (जैसे संचालन अनुसंधान) बाधा प्रोग्रामिंग को अधिकांशतः परिमित डोमेन पर बाधा प्रोग्रामिंग के साथ पहचाना जाता है।
परिमित डोमेन काँस्ट्रैंट प्रोग्रामिंग के सबसे सफल डोमेन में से है। कुछ क्षेत्रों में (जैसे संचालन अनुसंधान) काँस्ट्रैंट प्रोग्रामिंग को अधिकांशतः परिमित डोमेन पर काँस्ट्रैंट प्रोग्रामिंग के साथ पहचाना जाता है।


== बाधा प्रचार ==
== काँस्ट्रैंट प्रचार ==
{{Main|Constraint propagation}}
{{Main|बाधा प्रचार}}
स्थानीय स्थिरता की स्थिति चर या बाधाओं के सबसेट की स्थिरता से संबंधित [[बाधा संतुष्टि समस्या]] के गुण हैं। उनका उपयोग खोज स्थान को कम करने और समस्या को हल करने में आसान बनाने के लिए किया जा सकता है। नोड संगति, चाप संगति और पथ संगति सहित विभिन्न प्रकार की स्थानीय संगति स्थितियों का लाभ उठाया जाता है।
 
प्रत्येक स्थानीय स्थिरता की स्थिति को परिवर्तन द्वारा लागू किया जा सकता है जो समस्या को उसके समाधान को बदले बिना बदल देता है। इस तरह के परिवर्तन को बाधा प्रचार कहा जाता है।<ref>{{Citation|last=Bessiere|first=Christian|chapter=Constraint Propagation|date=2006|pages=29–83|publisher=Elsevier|isbn=9780444527264|doi=10.1016/s1574-6526(06)80007-6|title=Handbook of Constraint Programming|volume=2|series=Foundations of Artificial Intelligence}}</ref> बाधा प्रसार चर के डोमेन को कम करके, बाधाओं को मजबूत करके या नए बनाकर काम करता है। इससे खोज स्थान में कमी आती है, जिससे समस्या को कुछ एल्गोरिदम द्वारा हल करना आसान हो जाता है। बाधा प्रसार का उपयोग असंतोष चेकर के रूप में भी किया जा सकता है, सामान्य रूप से अपूर्ण किन्तु कुछ विशेष स्थिति में पूर्ण।
 
== बाधा समाधान ==
बाधा संतुष्टि समस्याओं को हल करने के लिए तीन मुख्य एल्गोरिथम तकनीकें हैं: बैकट्रैकिंग खोज, स्थानीय खोज और गतिशील प्रोग्रामिंग।<ref name=":0" />


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


प्रत्येक स्थानीय स्थिरता की स्थिति को परिवर्तन द्वारा लागू किया जा सकता है जो समस्या को उसके समाधान को बदले बिना परिवर्तित कर देता है। इस प्रकार के परिवर्तन को काँस्ट्रैंट प्रचार कहा जाता है।<ref>{{Citation|last=Bessiere|first=Christian|chapter=Constraint Propagation|date=2006|pages=29–83|publisher=Elsevier|isbn=9780444527264|doi=10.1016/s1574-6526(06)80007-6|title=Handbook of Constraint Programming|volume=2|series=Foundations of Artificial Intelligence}}</ref> काँस्ट्रैंट प्रसार चर के डोमेन को कम करके, काँस्ट्रैंटओं को मजबूत करके या नए बनाकर काम करता है। इससे खोज स्थान में कमी आती है, जिससे समस्या को कुछ एल्गोरिदम द्वारा हल करना आसान हो जाता है। काँस्ट्रैंट प्रसार का उपयोग असंतोष चेकर के रूप में भी किया जा सकता है, सामान्य रूप से अपूर्ण किन्तु कुछ विशेष स्थिति में पूर्ण।


== काँस्ट्रैंट समाधान ==
काँस्ट्रैंट संतुष्टि समस्याओं को हल करने के लिए तीन मुख्य एल्गोरिथम तकनीकें हैं: बैकट्रैकिंग खोज, स्थानीय खोज और गतिशील प्रोग्रामिंग।<ref name=":0" />
=== बैकट्रैकिंग खोज ===
=== बैकट्रैकिंग खोज ===
{{Main|Backtracking}}
{{Main|बैक ट्रैकिंग}}
बैकट्रैकिंग खोज कुछ [[कम्प्यूटेशनल समस्या]] के सभी (या कुछ) समाधानों को खोजने के लिए सामान्य [[कलन विधि]] है, विशेष रूप से संतुष्टि की समस्या, जो समाधान के लिए उम्मीदवारों को बढ़ती है, और जैसे ही यह निर्धारित करता है कि उम्मीदवार संभवतः नहीं हो सकता है, उम्मीदवार (बैकट्रैक) को छोड़ देता है। वैध समाधान के लिए पूरा किया गया।
बैकट्रैकिंग खोज कुछ [[कम्प्यूटेशनल समस्या|कम्प्यूटरीकृत समस्या]] के सभी (या कुछ) समाधानों को खोजने के लिए सामान्य [[कलन विधि]] है, विशेष रूप से संतुष्टि की समस्या, जो समाधान के लिए उम्मीदवारों को बढ़ती है, और जैसे ही यह निर्धारित करता है कि उम्मीदवार संभवतः नहीं हो सकता है, उम्मीदवार (बैकट्रैक) को छोड़ देता है। वैध समाधान के लिए पूरा किया गया हैं।


=== स्थानीय खोज ===
=== स्थानीय खोज ===
{{Main|Local search (constraint satisfaction)}}
{{Main|स्थानीय खोज (बाधा संतुष्टि)}}
एक बाधा संतुष्टि समस्या का समाधान खोजने के लिए स्थानीय खोज अपूर्ण विधि है। यह सभी बाधाओं के संतुष्ट होने तक चर के असाइनमेंट में क्रमिक रूप से सुधार करने पर आधारित है। विशेष रूप से, स्थानीय खोज एल्गोरिदम सामान्यतः प्रत्येक चरण में असाइनमेंट में चर के मान को संशोधित करते हैं। नया असाइनमेंट असाइनमेंट के स्थान में पिछले असाइनमेंट के करीब है, इसलिए इसका नाम ''स्थानीय खोज'' रखा गया है।
 
काँस्ट्रैंट संतुष्टि समस्या का समाधान खोजने के लिए स्थानीय खोज अपूर्ण विधि है। यह सभी काँस्ट्रैंटओं के संतुष्ट होने तक चर के असाइनमेंट में क्रमिक रूप से सुधार करने पर आधारित है। विशेष रूप से, स्थानीय खोज एल्गोरिदम सामान्यतः प्रत्येक चरण में असाइनमेंट में चर के मान को संशोधित करते हैं। नया असाइनमेंट असाइनमेंट के स्थान में पिछले असाइनमेंट के समीप है, इसलिए इसका नाम ''स्थानीय खोज'' रखा गया है।


=== गतिशील प्रोग्रामिंग ===
=== गतिशील प्रोग्रामिंग ===
{{Main|Dynamic programming}}
{{Main|गतिशील प्रोग्रामिंग}}
गतिशील प्रोग्रामिंग [[गणितीय अनुकूलन]] विधि और कंप्यूटर प्रोग्रामिंग विधि दोनों है। यह जटिल समस्या को पुनरावर्ती तरीके से सरल उप-समस्याओं में तोड़कर सरल बनाने के लिए संदर्भित करता है। जबकि कुछ निर्णय समस्याओं को इस तरह से अलग नहीं किया जा सकता है, ऐसे निर्णय जो समय में कई बिंदुओं को फैलाते हैं, अधिकांशतः पुनरावर्ती रूप से अलग हो जाते हैं। इसी तरह, कंप्यूटर विज्ञान में, यदि किसी समस्या को उप-समस्याओं में तोड़कर और फिर पुनरावर्ती रूप से उप-समस्याओं का इष्टतम समाधान ढूंढकर हल किया जा सकता है, तो इसे इष्टतम उप-संरचना कहा जाता है।
गतिशील प्रोग्रामिंग [[गणितीय अनुकूलन]] विधि और कंप्यूटर प्रोग्रामिंग विधि दोनों है। यह जटिल समस्या को पुनरावर्ती तरीके से सरल उप-समस्याओं में तोड़कर सरल बनाने के लिए संदर्भित करता है। जबकि कुछ निर्णय समस्याओं को इस प्रकार से अलग नहीं किया जा सकता है, ऐसे निर्णय जो समय में कई बिंदुओं को फैलाते हैं, अधिकांशतः पुनरावर्ती रूप से अलग हो जाते हैं। इसी प्रकार, कंप्यूटर विज्ञान में, यदि किसी समस्या को उप-समस्याओं में तोड़कर और फिर पुनरावर्ती रूप से उप-समस्याओं का इष्टतम समाधान ढूंढकर हल किया जा सकता है, तो इसे इष्टतम उप-संरचना कहा जाता है।


== उदाहरण ==
== उदाहरण ==
परिमित डोमेन पर बाधाओं को व्यक्त करने के लिए सिंटैक्स मेजबान भाषा पर निर्भर करता है। निम्नलिखित प्रोलॉग प्रोग्राम है जो क्लासिकल [[अक्षरात्मक]] पहेली वर्बल अंकगणित को हल करता है|SEND+MORE=MONEY in Constraint Logic Programming:
परिमित डोमेन पर काँस्ट्रैंटओं को व्यक्त करने के लिए सिंटैक्स मेजबान भाषा पर निर्भर करता है। निम्नलिखित प्रोलॉग प्रोग्राम है जो क्लासिकल [[अक्षरात्मक]] पहेली वर्बल अंकगणित को हल करता है। SEND+MORE=MONEY काँस्ट्रैंट तर्क प्रोग्रामिंग में:
<वाक्यविन्यास लैंग = प्रोलॉग>
 
% यह कोड YAP और SWI-Prolog दोनों में पर्यावरण-प्रदत्त का उपयोग करके काम करता है
यह कोड YAP और SWI-Prolog दोनों में पर्यावरण-प्रदत्त का उपयोग करके काम करता है
% CLPFD कंस्ट्रेंट सॉल्वर लाइब्रेरी। इसे काम करने के लिए मामूली संशोधनों की आवश्यकता हो सकती है
 
अन्य प्रोलॉग वातावरण में% या अन्य बाधा हलकों का उपयोग करना।
CLPFD कंस्ट्रेंट सॉल्वर लाइब्रेरी के लिए काम करने के लिए सरल संशोधनों की आवश्यकता हो सकती है
 
अन्य प्रोलॉग वातावरण में% या अन्य काँस्ट्रैंट हल कों का उपयोग किया जाता हैं।
: - use_module (लाइब्रेरी (clpfd))।
: - use_module (लाइब्रेरी (clpfd))।
सेंडमोर (अंक) :-
% CLPFD constraint solver library.  It may require minor modifications to work
  अंक = [एस, , एन, डी, एम, , आर, वाई],% चर बनाएँ
% in other Prolog environments or using other constraint solvers.
  अंक ins 0..9,,% डोमेन को वेरिएबल से संबद्ध करें
:- use_module(library(clpfd)).
  एस #\= 0,0% बाधा: एस 0 से अलग होना चाहिए
sendmore(Digits) :-
  एम #\= 0,
    Digits = [S,E,N,D,M,O,R,Y],   % Create variables
  all_अलग (अंक),% सभी तत्वों को अलग-अलग मान लेना चाहिए
    Digits ins 0..9,               % Associate domains to variables
  1000*एस + 100*+ 10*एन + डी�% अन्य बाधाएं
    S #\= 0,                       % Constraint: S must be different from 0
  + 1000*एम + 100*+ 10*आर +
    M #\= 0,
  #= 10000*एम + 1000*+ 100*एन + 10*+ वाई,
    all_different(Digits),         % all the elements must take different values
  लेबल (अंक)।�% खोज प्रारंभ करें
                1000*S + 100*E + 10*N + D    % Other constraints
</वाक्यविन्यास हाइलाइट>
              + 1000*M + 100*O + 10*R + E
    #= 10000*M + 1000*O + 100*N + 10*E + Y,


दुभाषिया पहेली में प्रत्येक अक्षर के लिए चर बनाता है। परिचालक <code>ins</code> इन वेरिएबल्स के डोमेन को निर्दिष्ट करने के लिए उपयोग किया जाता है, जिससे कि वे मानों के सेट {0,1,2,3, ..., 9} पर रेंज कर सकें। विवशताएँ <code>S#\=0</code> और <code>M#\=0</code> इसका अर्थ है कि ये दो चर मान शून्य नहीं ले सकते। जब दुभाषिया इन बाधाओं का मूल्यांकन करता है, तो यह इन दो चरों के डोमेन को उनमें से मान 0 हटाकर कम कर देता है। फिर, विवशता <code>all_different(Digits)</code> माना जाता है; यह किसी भी डोमेन को कम नहीं करता है, इसलिए इसे केवल स्टोर किया जाता है। अंतिम बाधा निर्दिष्ट करती है कि अक्षरों को निर्दिष्ट अंक ऐसे होने चाहिए कि SEND+MORE=MONEY धारण करे जब प्रत्येक अक्षर को उसके संबंधित अंक से बदल दिया जाए। इस बाधा से, सॉल्वर का अनुमान है कि एम = 1। वेरिएबल M से जुड़े सभी संग्रहित प्रतिबंध जागृत हो जाते हैं: इस स्थिति में, पर बाधा प्रसार <code>all_different</code> बाधा शेष सभी चर के डोमेन से मान 1 को हटा देती है। बाधा प्रचार सभी डोमेन को मान में कम करके समस्या को हल कर सकता है, यह सिद्ध कर सकता है कि डोमेन को खाली सेट में कम करके समस्या का कोई समाधान नहीं है, किन्तु संतुष्टि या असंतोषजनकता सिद्ध किए बिना भी समाप्त हो सकता है। लेबल लिटरल का उपयोग वास्तव में किसी समाधान की खोज करने के लिए किया जाता है।
    label(Digits).                  % Start the search
दुभाषिया पहेली में प्रत्येक अक्षर के लिए चर बनाता है। परिचालक <code>ins</code> इन वेरिएबल्स के डोमेन को निर्दिष्ट करने के लिए उपयोग किया जाता है, जिससे कि वे मानों के समुच्चय {0,1,2,3, ..., 9} पर सीमा का उपयोग कर सकें। विवशताएँ <code>S#\=0</code> और <code>M#\=0</code> इसका अर्थ है कि ये दो चर मान शून्य नहीं ले सकते। जब दुभाषिया इन काँस्ट्रैंटओं का मूल्यांकन करता है, तो यह इन दो चरों के डोमेन को उनमें से मान 0 हटाकर कम कर देता है। फिर, विवशता <code>all_different(Digits)</code> माना जाता है; यह किसी भी डोमेन को कम नहीं करता है, इसलिए इसे केवल स्टोर किया जाता है। अंतिम काँस्ट्रैंट निर्दिष्ट करती है कि अक्षरों को निर्दिष्ट अंक ऐसे होने चाहिए कि SEND+MORE=MONEY धारण करे जब प्रत्येक अक्षर को उसके संबंधित अंक से परिर्वतित कर दिया जाता हैं। इस काँस्ट्रैंट से, सॉल्वर का अनुमान है कि एम = 1। वेरिएबल M से जुड़े सभी संग्रहित प्रतिबंध जागृत हो जाते हैं: इस स्थिति में, पर काँस्ट्रैंट प्रसार <code>all_different</code> काँस्ट्रैंट शेष सभी चर के डोमेन से मान 1 को हटा देती है। काँस्ट्रैंट प्रचार सभी डोमेन को मान में कम करके समस्या को हल कर सकता है, यह सिद्ध कर सकता है कि डोमेन को रिक्त समुच्चय में कम करके समस्या का कोई समाधान नहीं है, किन्तु संतुष्टि या असंतोषजनकता सिद्ध किए बिना भी समाप्त हो सकता है। लेबल लिटरल का उपयोग वास्तव में किसी समाधान की खोज करने के लिए किया जाता है।


== यह भी देखें ==
== यह भी देखें ==
* [[संयुक्त अनुकूलन]]
* [[संयुक्त अनुकूलन]]
* बाधा तर्क प्रोग्रामिंग
* काँस्ट्रैंट लॉजिकल प्रोग्रामिंग
* [[समवर्ती बाधा तर्क प्रोग्रामिंग]]
* [[समवर्ती बाधा तर्क प्रोग्रामिंग|समवर्ती काँस्ट्रैंट लॉजिकल प्रोग्रामिंग]]
* गणितीय अनुकूलन
* गणितीय अनुकूलन
* अनुमानी (कंप्यूटर विज्ञान)
* अनुमानी (कंप्यूटर विज्ञान)
Line 149: Line 151:


==बाहरी संबंध==
==बाहरी संबंध==
{{Commonscat}}
*[http://www.a4cp.org/ Association for Constraint Programming]
*[http://www.a4cp.org/ Association for Constraint Programming]
*[http://www.a4cp.org/events/cp-conference-series CP Conference Series]
*[http://www.a4cp.org/events/cp-conference-series CP Conference Series]
Line 157: Line 158:
*[https://sofdem.github.io/gccat/index.html Global Constraint Catalog]
*[https://sofdem.github.io/gccat/index.html Global Constraint Catalog]


{{Types of programming languages}}
[[Category:Articles with hatnote templates targeting a nonexistent page]]
 
[[Category:CS1 English-language sources (en)]]
[[Category: बाधा प्रोग्रामिंग | बाधा प्रोग्रामिंग ]] [[Category: प्रोग्रामिंग प्रतिमान]] [[Category: घोषणात्मक प्रोग्रामिंग]]
 
 
 
[[Category: Machine Translated Page]]
[[Category:Created On 13/02/2023]]
[[Category:Created On 13/02/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Webarchive template archiveis links]]
[[Category:घोषणात्मक प्रोग्रामिंग]]
[[Category:प्रोग्रामिंग प्रतिमान]]
[[Category:बाधा प्रोग्रामिंग| बाधा प्रोग्रामिंग ]]

Latest revision as of 13:16, 14 September 2023

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

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

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

काँस्ट्रैंट लॉजिकल प्रोग्रामिंग

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

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

काँस्ट्रैंट प्रोग्रामिंग दृष्टिकोण दुनिया की ऐसी स्थिति की खोज करना है जिसमें बड़ी संख्या में काँस्ट्रैंटएं ही समय में संतुष्ट हों। समस्या को सामान्यतः दुनिया की ऐसी स्थिति के रूप में कहा जाता है जिसमें कई अज्ञात चर होते हैं। काँस्ट्रैंट फंक्शन सभी चर के लिए इसके मानों की खोज करता है।

टेम्पोरल समवर्ती काँस्ट्रैंट प्रोग्रामिंग (TCC) और गैर-नियतात्मक लौकिक समवर्ती काँस्ट्रैंट प्रोग्रामिंग (MJV) काँस्ट्रैंट प्रोग्रामिंग के प्रकार हैं जो समय के साथ निपट सकते हैं।

काँस्ट्रैंट संतुष्टि समस्या

एक काँस्ट्रैंट कई चर के बीच संबंध है जो उन मूल्यों को सीमित करता है जो ये चर साथ ले सकते हैं।

परिभाषा — परिमित डोमेन (या सीएसपी) पर एक बाधा संतुष्टि समस्या को ट्रिपलेट द्वारा परिभाषित किया गया है जहाँ:

  • समस्या के चरों का समुच्चय है;
  • चर के डोमेन का सेट है, यानी सभी के लिए हमारे पास ;
  • बाधाओं का एक समूह है। एक स्थिरांक एक समुच्चय के रूप में दर्शाया जाता हैं चर और एक संबंध जो चर के लिए एक साथ अनुमत मानों के सेट को परिभाषित करता है :

काँस्ट्रैंटओं की तीन श्रेणियां सम्मलित हैं:

  • विस्तृत काँस्ट्रैंटएँ: काँस्ट्रैंटओं को उन मूल्यों के समूह की गणना करके परिभाषित किया जाता है जो उन्हें संतुष्ट करेंगे;
  • अंकगणितीय काँस्ट्रैंटएँ: काँस्ट्रैंटओं को अंकगणितीय अभिव्यक्ति द्वारा परिभाषित किया जाता है, अर्थात का उपयोग करना
  • लॉजिकल काँस्ट्रैंटएँ: काँस्ट्रैंटओं को स्पष्ट शब्दार्थ के साथ परिभाषित किया गया है, अर्थात, सभी अलग, सबसे ज्यादा,...

परिभाषा — एक असाइनमेंट (या मॉडल) एक सीएसपी का युगल द्वारा परिभाषित किया गया है जहां:

  • </nowiki> चर का सबसमुच्चय है;
  • असाइन किए गए वेरिएबल्स द्वारा लिए गए मानों का टपल है।

एसाइमेंट वेरिएबल का उसके डोमेन के मान से जुड़ाव है। आंशिक असाइनमेंट तब होता है जब समस्या के चर का सबसमुच्चय असाइन किया गया हो। कुल असाइनमेंट तब होता है जब समस्या के सभी चर असाइन किए गए हों।

Property — Given an assignation (partial or total) of a CSP , and a constraint of such as , the assignation satisfies the constraint if and only if all the values of the variables of the constraint belongs to .

परिभाषा — सीएसपी का एक समाधान कुल असाइनमेंट है जो समस्या की सभी बाधाओं को संतुष्ट करता है।

सीएसपी के समाधान की खोज के समय, उपयोगकर्ता निम्नलिखित की इच्छा कर सकता है:

  • एक समाधान खोजना (सभी काँस्ट्रैंटओं को पूरा करना);
  • समस्या के सभी समाधान खोजना;
  • समस्या की असंतोषजनकता को सिद्ध करना।

काँस्ट्रैंट अनुकूलन समस्या

काँस्ट्रैंट अनुकूलन समस्या (COP) वस्तुनिष्ठ कार्य से जुड़ी काँस्ट्रैंट संतुष्टि समस्या है।

न्यूनीकरण (अधिकतमकरण) सीओपी का इष्टतम समाधान समाधान है जो उद्देश्य समारोह के मूल्य को कम करता है (अधिकतम करता है)।

सीएसपी के समाधान की खोज के समय, उपयोगकर्ता निम्नलिखित की इच्छा कर सकता है:

  • समाधान खोजना (सभी काँस्ट्रैंटओं को पूरा करना);
  • उद्देश्य के संबंध में सबसे अच्छा समाधान खोजना;
  • सर्वोत्तम पाए गए समाधान की इष्टतमता सिद्ध करना;
  • समस्या की असंतोषजनकता को सिद्ध करना।

त्रुटि तथा शोधन मॉडल में अंतर

काँस्ट्रैंट-आधारित प्रोग्रामिंग के लिए भाषाएँ दो दृष्टिकोणों में से का अनुसरण करती हैं:[3]

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

काँस्ट्रैंट संतुष्टि समस्याओं में काँस्ट्रैंट प्रसार परिशोधन मॉडल का विशिष्ट उदाहरण है, और स्प्रेडशीट गड़बड़ी मॉडल का विशिष्ट उदाहरण है।

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

डोमेन

काँस्ट्रैंट प्रोग्रामिंग में उपयोग की जाने वाली काँस्ट्रैंटएँ सामान्यतः कुछ विशिष्ट डोमेन पर होती हैं। काँस्ट्रैंट प्रोग्रामिंग के लिए कुछ लोकप्रिय डोमेन हैं:

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

परिमित डोमेन काँस्ट्रैंट प्रोग्रामिंग के सबसे सफल डोमेन में से है। कुछ क्षेत्रों में (जैसे संचालन अनुसंधान) काँस्ट्रैंट प्रोग्रामिंग को अधिकांशतः परिमित डोमेन पर काँस्ट्रैंट प्रोग्रामिंग के साथ पहचाना जाता है।

काँस्ट्रैंट प्रचार

स्थानीय स्थिरता की स्थिति चर या काँस्ट्रैंटओं के सबसमुच्चय की स्थिरता से संबंधित काँस्ट्रैंट संतुष्टि समस्या के गुण हैं। उनका उपयोग खोज स्थान को कम करने और समस्या को हल करने में आसान बनाने के लिए किया जा सकता है। नोड संगति, चाप संगति और पथ संगति सहित विभिन्न प्रकार की स्थानीय संगति स्थितियों का लाभ उठाया जाता है।

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

काँस्ट्रैंट समाधान

काँस्ट्रैंट संतुष्टि समस्याओं को हल करने के लिए तीन मुख्य एल्गोरिथम तकनीकें हैं: बैकट्रैकिंग खोज, स्थानीय खोज और गतिशील प्रोग्रामिंग।[1]

बैकट्रैकिंग खोज

बैकट्रैकिंग खोज कुछ कम्प्यूटरीकृत समस्या के सभी (या कुछ) समाधानों को खोजने के लिए सामान्य कलन विधि है, विशेष रूप से संतुष्टि की समस्या, जो समाधान के लिए उम्मीदवारों को बढ़ती है, और जैसे ही यह निर्धारित करता है कि उम्मीदवार संभवतः नहीं हो सकता है, उम्मीदवार (बैकट्रैक) को छोड़ देता है। वैध समाधान के लिए पूरा किया गया हैं।

स्थानीय खोज

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

गतिशील प्रोग्रामिंग

गतिशील प्रोग्रामिंग गणितीय अनुकूलन विधि और कंप्यूटर प्रोग्रामिंग विधि दोनों है। यह जटिल समस्या को पुनरावर्ती तरीके से सरल उप-समस्याओं में तोड़कर सरल बनाने के लिए संदर्भित करता है। जबकि कुछ निर्णय समस्याओं को इस प्रकार से अलग नहीं किया जा सकता है, ऐसे निर्णय जो समय में कई बिंदुओं को फैलाते हैं, अधिकांशतः पुनरावर्ती रूप से अलग हो जाते हैं। इसी प्रकार, कंप्यूटर विज्ञान में, यदि किसी समस्या को उप-समस्याओं में तोड़कर और फिर पुनरावर्ती रूप से उप-समस्याओं का इष्टतम समाधान ढूंढकर हल किया जा सकता है, तो इसे इष्टतम उप-संरचना कहा जाता है।

उदाहरण

परिमित डोमेन पर काँस्ट्रैंटओं को व्यक्त करने के लिए सिंटैक्स मेजबान भाषा पर निर्भर करता है। निम्नलिखित प्रोलॉग प्रोग्राम है जो क्लासिकल अक्षरात्मक पहेली वर्बल अंकगणित को हल करता है। SEND+MORE=MONEY काँस्ट्रैंट तर्क प्रोग्रामिंग में:

यह कोड YAP और SWI-Prolog दोनों में पर्यावरण-प्रदत्त का उपयोग करके काम करता है

CLPFD कंस्ट्रेंट सॉल्वर लाइब्रेरी के लिए काम करने के लिए सरल संशोधनों की आवश्यकता हो सकती है

अन्य प्रोलॉग वातावरण में% या अन्य काँस्ट्रैंट हल कों का उपयोग किया जाता हैं।

- use_module (लाइब्रेरी (clpfd))।
% CLPFD constraint solver library.  It may require minor modifications to work
% in other Prolog environments or using other constraint solvers.
:- use_module(library(clpfd)).
sendmore(Digits) :-
   Digits = [S,E,N,D,M,O,R,Y],   % Create variables
   Digits ins 0..9,                % Associate domains to variables
   S #\= 0,                        % Constraint: S must be different from 0
   M #\= 0,
   all_different(Digits),          % all the elements must take different values
                1000*S + 100*E + 10*N + D     % Other constraints
              + 1000*M + 100*O + 10*R + E
   #= 10000*M + 1000*O + 100*N + 10*E + Y,
   label(Digits).                  % Start the search

दुभाषिया पहेली में प्रत्येक अक्षर के लिए चर बनाता है। परिचालक ins इन वेरिएबल्स के डोमेन को निर्दिष्ट करने के लिए उपयोग किया जाता है, जिससे कि वे मानों के समुच्चय {0,1,2,3, ..., 9} पर सीमा का उपयोग कर सकें। विवशताएँ S#\=0 और M#\=0 इसका अर्थ है कि ये दो चर मान शून्य नहीं ले सकते। जब दुभाषिया इन काँस्ट्रैंटओं का मूल्यांकन करता है, तो यह इन दो चरों के डोमेन को उनमें से मान 0 हटाकर कम कर देता है। फिर, विवशता all_different(Digits) माना जाता है; यह किसी भी डोमेन को कम नहीं करता है, इसलिए इसे केवल स्टोर किया जाता है। अंतिम काँस्ट्रैंट निर्दिष्ट करती है कि अक्षरों को निर्दिष्ट अंक ऐसे होने चाहिए कि SEND+MORE=MONEY धारण करे जब प्रत्येक अक्षर को उसके संबंधित अंक से परिर्वतित कर दिया जाता हैं। इस काँस्ट्रैंट से, सॉल्वर का अनुमान है कि एम = 1। वेरिएबल M से जुड़े सभी संग्रहित प्रतिबंध जागृत हो जाते हैं: इस स्थिति में, पर काँस्ट्रैंट प्रसार all_different काँस्ट्रैंट शेष सभी चर के डोमेन से मान 1 को हटा देती है। काँस्ट्रैंट प्रचार सभी डोमेन को मान में कम करके समस्या को हल कर सकता है, यह सिद्ध कर सकता है कि डोमेन को रिक्त समुच्चय में कम करके समस्या का कोई समाधान नहीं है, किन्तु संतुष्टि या असंतोषजनकता सिद्ध किए बिना भी समाप्त हो सकता है। लेबल लिटरल का उपयोग वास्तव में किसी समाधान की खोज करने के लिए किया जाता है।

यह भी देखें

संदर्भ

  1. 1.0 1.1 Rossi, Francesca; Beek, Peter van; Walsh, Toby (2006-08-18). Handbook of Constraint Programming (in English). Elsevier. ISBN 9780080463803.
  2. Jaffar, Joxan, and J-L. Lassez. "Constraint logic programming." Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. ACM, 1987.
  3. Mayoh, Brian; Tyugu, Enn; Penjam, Jaan (1993). Constraint Programming. Springer Science+Business Media. p. 76. ISBN 9783642859830.
  4. Lopez, G., Freeman-Benson, B., & Borning, A. (1994, January). Kaleidoscope: A constraint imperative programming language. In Constraint Programming (pp. 313-329). Springer Berlin Heidelberg.
  5. Bessiere, Christian (2006), "Constraint Propagation", Handbook of Constraint Programming, Foundations of Artificial Intelligence, vol. 2, Elsevier, pp. 29–83, doi:10.1016/s1574-6526(06)80007-6, ISBN 9780444527264


बाहरी संबंध