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

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

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

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

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

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

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

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

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

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

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

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

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

परिभाषा — परिमित डोमेन (या सीएसपी) पर एक बाधा संतुष्टि समस्या को ट्रिपलेट द्वारा परिभाषित किया गया है $({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ जहाँ:

• ${\mathcal {X}}=\{x_{1},\dots ,x_{n}\}$ समस्या के चरों का समुच्चय है;
• ${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ चर के डोमेन का सेट है, यानी सभी के लिए $k\in [1;n]$ हमारे पास $x_{k}\in {\mathcal {D}}_{k}$;
• ${\mathcal {C}}=\{C_{1},\dots ,C_{m}\}$ बाधाओं का एक समूह है। एक स्थिरांक $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ एक समुच्चय के रूप में दर्शाया जाता हैं ${\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}$ चर और एक संबंध ${\mathcal {R}}_{i}\subset {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}$ जो चर के लिए एक साथ अनुमत मानों के सेट को परिभाषित करता है ${\mathcal {X}}_{i}$:

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

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

परिभाषा — एक असाइनमेंट (या मॉडल) ${\mathcal {A}}$ एक सीएसपी का $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ युगल द्वारा परिभाषित किया गया है ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ जहां:

• ${\mathcal {X_{\mathcal {A}}}}\subset {\mathcal {X}}<nowiki>$</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}}\}$ असाइन किए गए वेरिएबल्स द्वारा लिए गए मानों का टपल है।

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

Property — Given ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ an assignation (partial or total) of a CSP $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$, and $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ a constraint of $P$ such as ${\mathcal {X}}_{i}\subset {\mathcal {X_{\mathcal {A}}}}$, the assignation ${\mathcal {A}}$ satisfies the constraint $C_{i}$ if and only if all the values ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ of the variables of the constraint $C_{i}$ belongs to ${\mathcal {R}}_{i}$.

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

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

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

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

Main article: विवश अनुकूलन

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

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

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

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

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

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

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

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

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

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

डोमेन

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

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

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

बाधा प्रचार

Main article: बाधा प्रचार

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

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

बाधा समाधान

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

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

Main article: बैक ट्रैकिंग

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

स्थानीय खोज

Main article: स्थानीय खोज (बाधा संतुष्टि)

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

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

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

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

उदाहरण

परिमित डोमेन पर बाधाओं को व्यक्त करने के लिए सिंटैक्स मेजबान भाषा पर निर्भर करता है। निम्नलिखित प्रोलॉग प्रोग्राम है जो क्लासिकल अक्षरात्मक पहेली वर्बल अंकगणित को हल करता है। 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 को हटा देती है। बाधा प्रचार सभी डोमेन को मान में कम करके समस्या को हल कर सकता है, यह सिद्ध कर सकता है कि डोमेन को रिक्त समुच्चय में कम करके समस्या का कोई समाधान नहीं है, किन्तु संतुष्टि या असंतोषजनकता सिद्ध किए बिना भी समाप्त हो सकता है। लेबल लिटरल का उपयोग वास्तव में किसी समाधान की खोज करने के लिए किया जाता है।

यह भी देखें

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

बाहरी संबंध

• 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