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

एक बाधा संतुष्टि समस्या चरों के एक समुच्चय को मानों के एक नियतन (assignment) के लिए पूछती है जो उनके बीच की सभी बाधाओं को एक साथ संतुष्ट करता है, जिससे कई संयोजनात्मक समस्याओं के लिए एक समान प्रतिनिधित्व मिलता है।

Definition

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

Scope

यह विषय बाधा संतुष्टि समस्या (CSP) औपचारिकता (चर, डोमेन, बाधाएँ) और इसे हल करने वाले एल्गोरिदम को शामिल करता है: चर- और मान-क्रमबद्धता अनुमानी (variable- and value-ordering heuristics) के साथ बैकट्रैकिंग खोज, बाधा प्रसार और संगति तकनीकें (नोड, आर्क, और पाथ संगति, जैसे AC-3 एल्गोरिथम), और समस्या संरचना का शोषण (वृक्ष-संरचित CSPs, कटसेट कंडीशनिंग)। यह CSPs के लिए स्थानीय खोज और बाधा प्रोग्रामिंग के व्यापक अभ्यास से जुड़ता है। समान समस्याओं के निरंतर-अनुकूलन और सीखने-आधारित सूत्रण यहाँ दायरे से बाहर हैं।

Core questions

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

Key concepts

• चर, डोमेन, बाधाएँ
• बाधा ग्राफ
• बैकट्रैकिंग खोज
• फॉरवर्ड चेकिंग
• आर्क संगति और AC-3
• न्यूनतम-शेष-मान अनुमानी
• बाधा प्रसार
• वृक्ष-संरचित CSPs और कटसेट कंडीशनिंग

Key theories

आर्क संगति और बाधा प्रसार

एक CSP आर्क संगत होता है जब प्रत्येक चर के प्रत्येक मान का प्रत्येक पड़ोसी चर में एक संगत साथी होता है; AC-3 जैसे एल्गोरिदम असमर्थित मानों को बार-बार हटाकर इसे लागू करते हैं, अक्सर खोज से पहले या उसके दौरान डोमेन को नाटकीय रूप से छोटा करते हैं।

अनुमानी के साथ बैकट्रैकिंग खोज

CSPs को बैकट्रैकिंग के साथ गहराई-पहली नियतन (depth-first assignment) द्वारा हल किया जाता है, जिसे सबसे-बाधित चर (न्यूनतम शेष मान), सबसे कम-बाधित मान का चयन करके, और डेड एंड का जल्दी पता लगाने के लिए फॉरवर्ड चेकिंग या प्रसार को अंतर्विरोधी करके व्यावहारिक बनाया जाता है।

संरचना का शोषण

जब बाधा ग्राफ एक वृक्ष होता है, तो एक CSP को चरों की संख्या के रैखिक समय में हल किया जा सकता है, और निकट-वृक्ष संरचनाओं को कटसेट कंडीशनिंग या वृक्ष अपघटन (tree decomposition) के माध्यम से इस मामले में कम किया जा सकता है।

Clinical relevance

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

History

बाधा नेटवर्क 1970 के दशक में दृश्य लेबलिंग और संबंधपरक संगति पर काम से उभरे, जिसमें मैकवर्थ के 1977 के पेपर ने नोड, आर्क और पाथ संगति को औपचारिक रूप दिया। 1980-90 के दशक के दौरान यह क्षेत्र बाधा प्रोग्रामिंग में परिपक्व हुआ, जिसे 2006 की हैंडबुक ऑफ कंस्ट्रेंट प्रोग्रामिंग में समेकित किया गया, और यह एक मानक AI विषय बना हुआ है।

Key figures

• Alan K. Mackworth
• Rina Dechter
• Eugene C. Freuder
• Ugo Montanari

Seminal works

• mackworth1977
• dechter2003
• rossi2006

Frequently asked questions

एक बाधा संतुष्टि समस्या एक सामान्य खोज समस्या से कैसे भिन्न है?

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

आर्क संगति क्या करती है?

आर्क संगति एक चर के डोमेन से उन मानों को हटा देती है जिनका पड़ोसी चर में कोई संगत मान नहीं होता है, उनके बीच की बाधा को देखते हुए। खोज से पहले और उसके दौरान इसे लागू करने से खोज स्थान छंट जाता है और कभी-कभी बैकट्रैकिंग के बिना सीधे समस्या को हल किया जा सकता है।