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

Introduction

एक बाधा संतुष्टि समस्या एक ऐसी समस्या है जिसे कुछ सीमाओं या शर्तों के भीतर इसके समाधान की आवश्यकता होती है जिसे बाधाओं के रूप में भी जाना जाता है।इसमें निम्न शामिल हैं

• चर का एक सीमित सेट जो समाधान को संग्रहीत करता है (V = {V1, V2, V3, ....., Vn})|
• एक ऐसा डोमेन जहां इन चर में से प्रत्येक का नक्शा होता है। डोमेन (D = {D1, D2, D3, D4 ... Dn) से संबंधित हैं|
• एक अच्छी तरह से परिभाषित गैर अनंत बाधाओं का सेट।

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

शुरुआत के दिन

लगातार संतुष्टि, निश्चित रूप से 1965 से पहले की है। वास्तविक दुनिया की समस्याएं जिन्हें हम अब काम संतुष्टि निर्धारण के रूप में बाधा संतुष्टि समस्याओं के रूप में पहचानते हैं, स्वाभाविक रूप से हमेशा हमारे साथ रहे हैं। कहा जाता है कि खिलौना 8-क्वीन की समस्या है, जो कृत्रिम बुद्धिमत्ता में कई शुरुआती अवरोधक संतुष्टि शोधकर्ताओं के लिए प्रचलित है, यह कहा जाता है कि 1848 में शतरंज खिलाड़ी मैक्स बाजेल द्वारा प्रस्तावित किया गया था। पौराणिक कथाओं का दावा है कि एक खोज का एक रूप है, एक शक्तिशाली खोज प्रतिमान जो एक केंद्रीय भी बन गया है|

सैद्धांतिक पहलू

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

बाधाओं के माध्यम से सूचना का प्रसार

• आगे की जाँच

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

• बाधा का प्रचार

निहितार्थ के प्रचार के लिए संयम प्रसार सामान्य शब्द है अन्य चर पर एक चर पर एक बाधा

• 

  रंग भरने की समस्या को हल करने में बाधा संतुष्टि समस्या वक्तव्य का उदाहरण

समाधान के तरीके

• उत्पन्न और परीक्षण

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

• बैक ट्रैकिंग

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

• एक बाधा संतुष्टि समस्या को देखते हुए, कई कार्य किए जा सकते हैं:

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