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

काँस्ट्रैंट प्रोग्रामिंग (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