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

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

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

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

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

Main article: Constraint logic programming

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

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

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

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

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

Main article: Constraint satisfaction problem

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

Definition — A constraint satisfaction problem on finite domains (or CSP) is defined by a triplet $({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ where:

• ${\mathcal {X}}=\{x_{1},\dots ,x_{n}\}$ is the set of variables of the problem;
• ${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ is the set of domains of the variables, i.e., for all $k\in [1;n]$ we have $x_{k}\in {\mathcal {D}}_{k}$;
• ${\mathcal {C}}=\{C_{1},\dots ,C_{m}\}$ is a set of constraints. A constraint $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ is defined by a set ${\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}$ of variables and a relation ${\mathcal {R}}_{i}\subset {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}$ which defines the set of values allowed simultaneously for the variables of ${\mathcal {X}}_{i}$:

बाधाओं की तीन श्रेणियां मौजूद हैं:

• विस्तृत बाधाएँ: बाधाओं को उन मूल्यों के समूह की गणना करके परिभाषित किया जाता है जो उन्हें संतुष्ट करेंगे;
• अंकगणितीय बाधाएँ: बाधाओं को एक अंकगणितीय अभिव्यक्ति द्वारा परिभाषित किया जाता है, अर्थात, उपयोग करना $<,>,\leq ,\geq ,=,\neq ,...$;
• तार्किक बाधाएँ: बाधाओं को एक स्पष्ट शब्दार्थ के साथ परिभाषित किया गया है, अर्थात, AllDifferent, AtMost,...

Definition —  An assignment (or model) ${\mathcal {A}}$ of a CSP $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ is defined by the couple ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ जहां:

• गणित> \mathcal{X_{\mathcal{A

} \subset \mathcal{X} </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 एक वेरिएबल का उसके डोमेन के मान से जुड़ाव है। एक आंशिक असाइनमेंट तब होता है जब समस्या के चर का एक सबसेट असाइन किया गया हो। कुल असाइनमेंट तब होता है जब समस्या के सभी चर असाइन किए गए हों।

Theorem — Property

Definition — A solution of a CSP is a total assignation which satisfied all the constraints of the problem.

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

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

बाधा अनुकूलन समस्या

Main article: Constrained optimization

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

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

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

• एक समाधान खोजना (सभी बाधाओं को पूरा करना);

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

गड़बड़ी बनाम शोधन मॉडल

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

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

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

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

डोमेन

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

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

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

बाधा प्रचार

Main article: Constraint propagation

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

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

बाधा समाधान

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

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

Main article: Backtracking

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

स्थानीय खोज

Main article: Local search (constraint satisfaction)

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

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

Main article: Dynamic programming

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

उदाहरण

परिमित डोमेन पर बाधाओं को व्यक्त करने के लिए सिंटैक्स मेजबान भाषा पर निर्भर करता है। निम्नलिखित एक प्रोलॉग प्रोग्राम है जो क्लासिकल अक्षरात्मक पहेली वर्बल अंकगणित को हल करता है|SEND+MORE=MONEY in Constraint Logic Programming: <वाक्यविन्यास लैंग = प्रोलॉग> % यह कोड YAP और SWI-Prolog दोनों में पर्यावरण-प्रदत्त का उपयोग करके काम करता है % CLPFD कंस्ट्रेंट सॉल्वर लाइब्रेरी। इसे काम करने के लिए मामूली संशोधनों की आवश्यकता हो सकती है अन्य प्रोलॉग वातावरण में% या अन्य बाधा हलकों का उपयोग करना।

- use_module (लाइब्रेरी (clpfd))।

सेंडमोर (अंक) :-

  अंक = [एस, ई, एन, डी, एम, ओ, आर, वाई],% चर बनाएँ
  अंक ins 0..9, % डोमेन को वेरिएबल से संबद्ध करें
  एस #\= 0, % बाधा: एस 0 से अलग होना चाहिए
  एम #\= 0,
  all_अलग (अंक),% सभी तत्वों को अलग-अलग मान लेना चाहिए
               1000*एस + 100*ई + 10*एन + डी % अन्य बाधाएं
             + 1000*एम + 100*ओ + 10*आर + ई
  #= 10000*एम + 1000*ओ + 100*एन + 10*ई + वाई,
  लेबल (अंक)। % खोज प्रारंभ करें

</वाक्यविन्यास हाइलाइट>

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

यह भी देखें

• संयुक्त अनुकूलन
• बाधा तर्क प्रोग्रामिंग
• समवर्ती बाधा तर्क प्रोग्रामिंग
• गणितीय अनुकूलन
• अनुमानी (कंप्यूटर विज्ञान)
• नर्स शेड्यूलिंग समस्या
• नियमित विवशता
• यात्रा टूर्नामेंट समस्या

बाहरी संबंध

• Association for Constraint Programming
• CP Conference Series
• Guide to Constraint Programming
• The Mozart Programming System at archive.today (archived December 5, 2012), an Oz-based free software (X11-style)
• Cork Constraint Computation Centre at archive.today (archived January 7, 2013)
• Global Constraint Catalog