2-संतोषजनकता: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Line 4: | Line 4: | ||
2-संतोषजनकता समस्या के उदाहरणों को सामान्यतः विशेष प्रकार के [[बूलियन तर्क]] के रूप में व्यक्त किया जाता है, जिसे [[संयोजक सामान्य रूप]] (2-सीएनएफ) या क्रॉम सूत्र कहा जाता है। वैकल्पिक रूप से, उन्हें विशेष प्रकार के [[निर्देशित ग्राफ]], [[निहितार्थ ग्राफ]] के रूप में व्यक्त किया जा सकता है, जो उदाहरण के वेरिएबल और उनके निषेधों को ग्राफ में शीर्ष के रूप में व्यक्त करता है, और वेरिएबल के जोड़े पर बाधाओं को निर्देशित किनारों के रूप में व्यक्त करता है। इन दोनों प्रकार के इनपुट को [[रैखिक समय]] में हल किया जा सकता है, या तो [[ बैक ट्रैकिंग |बैक ट्रैकिंग]] पर आधारित विधि द्वारा या निहितार्थ ग्राफ के दृढ़ता से जुड़े अवयवों का उपयोग करते है| रिज़ॉल्यूशन (तर्क), अतिरिक्त वैध बाधाओं को बनाने के लिए बाधाओं के जोड़े को संयोजित करने की विधि, बहुपद समय समाधान की ओर भी ले जाती है। 2-संतोषजनक समस्याएं संयोजक सामान्य रूप सूत्रों के दो प्रमुख उपवर्गों में से प्रदान करती हैं जिन्हें बहुपद समय में हल किया जा सकता है; दो उपवर्गों में से दूसरा हॉर्न-संतुष्टि है । | 2-संतोषजनकता समस्या के उदाहरणों को सामान्यतः विशेष प्रकार के [[बूलियन तर्क]] के रूप में व्यक्त किया जाता है, जिसे [[संयोजक सामान्य रूप]] (2-सीएनएफ) या क्रॉम सूत्र कहा जाता है। वैकल्पिक रूप से, उन्हें विशेष प्रकार के [[निर्देशित ग्राफ]], [[निहितार्थ ग्राफ]] के रूप में व्यक्त किया जा सकता है, जो उदाहरण के वेरिएबल और उनके निषेधों को ग्राफ में शीर्ष के रूप में व्यक्त करता है, और वेरिएबल के जोड़े पर बाधाओं को निर्देशित किनारों के रूप में व्यक्त करता है। इन दोनों प्रकार के इनपुट को [[रैखिक समय]] में हल किया जा सकता है, या तो [[ बैक ट्रैकिंग |बैक ट्रैकिंग]] पर आधारित विधि द्वारा या निहितार्थ ग्राफ के दृढ़ता से जुड़े अवयवों का उपयोग करते है| रिज़ॉल्यूशन (तर्क), अतिरिक्त वैध बाधाओं को बनाने के लिए बाधाओं के जोड़े को संयोजित करने की विधि, बहुपद समय समाधान की ओर भी ले जाती है। 2-संतोषजनक समस्याएं संयोजक सामान्य रूप सूत्रों के दो प्रमुख उपवर्गों में से प्रदान करती हैं जिन्हें बहुपद समय में हल किया जा सकता है; दो उपवर्गों में से दूसरा हॉर्न-संतुष्टि है । | ||
2-संतोषजनकता को ज्यामिति और विज़ुअलाइज़ेशन समस्याओं पर प्रयुक्त किया जा सकता है जिसमें वस्तुओं के संग्रह में प्रत्येक के दो संभावित स्थान होते हैं और लक्ष्य प्रत्येक वस्तु के लिए प्लेसमेंट | 2-संतोषजनकता को ज्यामिति और विज़ुअलाइज़ेशन समस्याओं पर प्रयुक्त किया जा सकता है जिसमें वस्तुओं के संग्रह में प्रत्येक के दो संभावित स्थान होते हैं और लक्ष्य प्रत्येक वस्तु के लिए प्लेसमेंट खोजता है जो अन्य वस्तुओं के साथ ओवरलैप होने से बचाता है। अन्य अनुप्रयोगों में क्लस्टर के व्यास के योग को कम करने के लिए क्लस्टरिंग डेटा, कक्षा और खेल शेड्यूलिंग और उनके क्रॉस-सेक्शन के बारे में जानकारी से आकृतियों को पुनर्प्राप्त करना सम्मिलित है। | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल सम्मिश्रता सिद्धांत]] में, 2-संतोषजनकता [[एनएल-पूर्ण]] समस्या का उदाहरण प्रदान करती है, जिसे | [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल सम्मिश्रता सिद्धांत]] में, 2-संतोषजनकता [[एनएल-पूर्ण]] समस्या का उदाहरण प्रदान करती है, जिसे संचयन की लघुगणकीय मात्रा का उपयोग करके गैर-नियतात्मक रूप से हल किया जा सकता है और यह इस संसाधन में हल करने योग्य सबसे कठिन समस्याओं में से है। 2-संतोषजनकता उदाहरण के सभी समाधानों के सेट को [[माध्यिका ग्राफ]] की संरचना दी जा सकती है, किन्तु इन समाधानों की गिनती शार्प-P-पूर्ण| या P-पूर्ण है और इसलिए बहुपद-समय समाधान की उम्मीद नहीं है। यादृच्छिक उदाहरणों को हल करने योग्य से अघुलनशील उदाहरणों में तेज चरण संक्रमण से गुजरना पड़ता है क्योंकि वेरिएबल के लिए बाधाओं का अनुपात 1 से अधिक बढ़ जाता है, घटना अनुमानित है किन्तु संतुष्टि समस्या के अधिक सम्मिश्र रूपों के लिए अप्रमाणित है। 2-संतोषजनकता की कम्प्यूटेशनल रूप से कठिन विविधता, सत्य असाइनमेंट खोजता जो संतुष्ट बाधाओं की संख्या को अधिकतम करता है, अनुमानित एल्गोरिदम है जिसकी अधिकतमता अद्वितीय गेम अनुमान पर निर्भर करती है, और और कठिन भिन्नता, वास्तविक वेरिएबल की संख्या को कम करने वाला संतोषजनक असाइनमेंट खोजता , [[पैरामीटरयुक्त जटिलता|पैरामीटर युक्त सम्मिश्रता]] के लिए महत्वपूर्ण परीक्षण स्तिथि है। | ||
==समस्या प्रतिनिधित्व == | ==समस्या प्रतिनिधित्व == | ||
| Line 17: | Line 17: | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
2-संतोषजनकता की समस्या इन वेरिएबलों के लिए [[सत्य असाइनमेंट|ट्रूथ असाइनमेंट]] | 2-संतोषजनकता की समस्या इन वेरिएबलों के लिए [[सत्य असाइनमेंट|ट्रूथ असाइनमेंट]] खोजता है जो पूरे सूत्र को सत्य बनाता है। ऐसा असाइनमेंट यह चुनता है कि प्रत्येक वेरिएबल को सही या गलत बनाया जाए, जिससे कि प्रत्येक खंड में कम से कम अक्षर सत्य हो जाए। ऊपर दिखाए गए अभिव्यक्ति के लिए, संभावित संतोषजनक असाइनमेंट वह है जो सभी सात वेरिएबलों को सत्य पर सेट करता है। प्रत्येक खंड में कम से कम गैर-ऋणात्मक वेरिएबल होता है, इसलिए यह असाइनमेंट प्रत्येक खंड को संतुष्ट करता है। सभी वेरिएबल्स को सेट करने की 15 अन्य विधियाँ भी हैं जिससे सूत्र सत्य हो जाए। इसलिए, इस अभिव्यक्ति द्वारा दर्शाया गया 2-संतोषजनक उदाहरण संतोषजनक है। | ||
इस रूप में सूत्रों को 2-सीएनएफ सूत्र के रूप में जाना जाता है। इस नाम में 2 प्रति खंड शाब्दिकों की संख्या को दर्शाता है, और सीएनएफ संयोजक सामान्य रूप के लिए है, विच्छेदन के संयोजन के रूप में प्रकार की बूलियन अभिव्यक्ति है।<ref name="cnf"/> कैलिफ़ोर्निया विश्वविद्यालय, डेविस के गणितज्ञ मेल्वेन आर. क्रॉम के कार्य के पश्चात, उन्हें क्रॉम सूत्र भी कहा जाता है, जिनका 1967 का पेपर 2-संतोषजनकता समस्या पर सबसे प्रारम्भिक कार्यों में से था।<ref name="Krom1967">{{citation | इस रूप में सूत्रों को 2-सीएनएफ सूत्र के रूप में जाना जाता है। इस नाम में 2 प्रति खंड शाब्दिकों की संख्या को दर्शाता है, और सीएनएफ संयोजक सामान्य रूप के लिए है, विच्छेदन के संयोजन के रूप में प्रकार की बूलियन अभिव्यक्ति है।<ref name="cnf"/> कैलिफ़ोर्निया विश्वविद्यालय, डेविस के गणितज्ञ मेल्वेन आर. क्रॉम के कार्य के पश्चात, उन्हें क्रॉम सूत्र भी कहा जाता है, जिनका 1967 का पेपर 2-संतोषजनकता समस्या पर सबसे प्रारम्भिक कार्यों में से था।<ref name="Krom1967">{{citation | ||
| Line 32: | Line 32: | ||
2-सीएनएफ सूत्र में प्रत्येक खंड वेरिएबल या अस्वीकृत वेरिएबल से दूसरे में निहितार्थ के लिए [[तार्किक तुल्यता]] है। उदाहरण के लिए, उदाहरण में दूसरा खंड तीन समकक्ष विधियों में से किसी में लिखा जा सकता है: | 2-सीएनएफ सूत्र में प्रत्येक खंड वेरिएबल या अस्वीकृत वेरिएबल से दूसरे में निहितार्थ के लिए [[तार्किक तुल्यता]] है। उदाहरण के लिए, उदाहरण में दूसरा खंड तीन समकक्ष विधियों में से किसी में लिखा जा सकता है: | ||
<math display="block">(x_0\lor\lnot x_3) \;\equiv\; (\lnot x_0\Rightarrow\lnot x_3) \;\equiv\; (x_3\Rightarrow x_0).</math> | <math display="block">(x_0\lor\lnot x_3) \;\equiv\; (\lnot x_0\Rightarrow\lnot x_3) \;\equiv\; (x_3\Rightarrow x_0).</math> | ||
इन विभिन्न प्रकार के ऑपरेशनों के | इन विभिन्न प्रकार के ऑपरेशनों के मध्य इस तुल्यता के कारण, 2-संतोषजनकता उदाहरण को निहितार्थ सामान्य रूप में भी लिखा जा सकता है, जिसमें हम संयोजनात्मक सामान्य रूप में प्रत्येक या खंड को उन दो निहितार्थों से प्रतिस्थापित करते हैं जिनके लिए यह समतुल्य है।<ref>{{citation|title=Artificial Intelligence: A Modern Approach|page=282|series=Prentice Hall series in artificial intelligence|first1=Stuart Jonathan|last1=Russell|first2=Peter|last2=Norvig|publisher=Prentice Hall|year=2010|isbn=978-0-13-604259-4}}.</ref> | ||
2-संतोषजनकता उदाहरण का वर्णन करने का तीसरा, अधिक ग्राफिकल विधि निहितार्थ ग्राफ के रूप में है। निहितार्थ ग्राफ निर्देशित ग्राफ है जिसमें प्रति वेरिएबल या ऋणात्मक वेरिएबल में शीर्ष (ग्राफ सिद्धांत) होता है, और शीर्ष को दूसरे से जोड़ने वाला किनारा होता है जब भी संबंधित वेरिएबल उदाहरण के निहितार्थ सामान्य रूप में निहितार्थ से संबंधित होते हैं। निहितार्थ ग्राफ [[तिरछा-सममित ग्राफ|विषम -सममित ग्राफ]] होना चाहिए, जिसका अर्थ है कि इसमें [[ग्राफ ऑटोमोर्फिज्म]] है जो प्रत्येक वेरिएबल को उसके निषेध में ले जाता है और सभी किनारों के झुकाव को | 2-संतोषजनकता उदाहरण का वर्णन करने का तीसरा, अधिक ग्राफिकल विधि निहितार्थ ग्राफ के रूप में है। निहितार्थ ग्राफ निर्देशित ग्राफ है जिसमें प्रति वेरिएबल या ऋणात्मक वेरिएबल में शीर्ष (ग्राफ सिद्धांत) होता है, और शीर्ष को दूसरे से जोड़ने वाला किनारा होता है जब भी संबंधित वेरिएबल उदाहरण के निहितार्थ सामान्य रूप में निहितार्थ से संबंधित होते हैं। निहितार्थ ग्राफ [[तिरछा-सममित ग्राफ|विषम -सममित ग्राफ]] होना चाहिए, जिसका अर्थ है कि इसमें [[ग्राफ ऑटोमोर्फिज्म]] है जो प्रत्येक वेरिएबल को उसके निषेध में ले जाता है और सभी किनारों के झुकाव को विपरीत कर देता है।<ref name="APT79">{{citation | ||
| last1 = Aspvall | first1 = Bengt | | last1 = Aspvall | first1 = Bengt | ||
| last2 = Plass | first2 = Michael F. | | last2 = Plass | first2 = Michael F. | ||
| Line 56: | Line 56: | ||
मान लीजिए कि 2-संतोषजनक उदाहरण में दो खंड हैं जो दोनों ही वेरिएबल x का उपयोग करते हैं, किन्तु x को खंड में नकार दिया गया है और दूसरे में नहीं। फिर दोनों खंडों को मिलाकर तीसरा खंड तैयार किया जा सकता है, जिसमें दो खंडों में दो अन्य शाब्दिक अर्थ होंगे; जब पहले दो खंड संतुष्ट हों तो यह तीसरा खंड भी संतुष्ट होना चाहिए। उदाहरण के लिए, हम खंडों <math>(a\lor b)</math> और <math>(\lnot b\lor\lnot c)</math> को जोड़ सकते हैं इस प्रकार <math>(a\lor\lnot c)</math> उपवाक्य का निर्माण करें . 2-सीएनएफ सूत्र के निहितार्थ रूप के संदर्भ में, यह नियम दो निहितार्थ खोजने <math>\lnot a\Rightarrow b</math> और <math>b\Rightarrow \lnot c</math> के समान है, और [[सकर्मक संबंध]] द्वारा तीसरे निहितार्थ <math>\lnot a\Rightarrow \lnot c</math> का अनुमान लगाना होता है .<ref name="Krom1967"/> | मान लीजिए कि 2-संतोषजनक उदाहरण में दो खंड हैं जो दोनों ही वेरिएबल x का उपयोग करते हैं, किन्तु x को खंड में नकार दिया गया है और दूसरे में नहीं। फिर दोनों खंडों को मिलाकर तीसरा खंड तैयार किया जा सकता है, जिसमें दो खंडों में दो अन्य शाब्दिक अर्थ होंगे; जब पहले दो खंड संतुष्ट हों तो यह तीसरा खंड भी संतुष्ट होना चाहिए। उदाहरण के लिए, हम खंडों <math>(a\lor b)</math> और <math>(\lnot b\lor\lnot c)</math> को जोड़ सकते हैं इस प्रकार <math>(a\lor\lnot c)</math> उपवाक्य का निर्माण करें . 2-सीएनएफ सूत्र के निहितार्थ रूप के संदर्भ में, यह नियम दो निहितार्थ खोजने <math>\lnot a\Rightarrow b</math> और <math>b\Rightarrow \lnot c</math> के समान है, और [[सकर्मक संबंध]] द्वारा तीसरे निहितार्थ <math>\lnot a\Rightarrow \lnot c</math> का अनुमान लगाना होता है .<ref name="Krom1967"/> | ||
क्रॉम लिखते हैं कि सूत्र <math>(x\lor x)</math> और <math> (\lnot x\lor\lnot x)</math> सुसंगत है यदि इस अनुमान नियम को निरंतर प्रयुक्त करने से दोनों खंड उत्पन्न नहीं हो सकते हैं , किसी भी <math> x</math>वेरिएबल के लिए. जैसा कि उन्होंने | क्रॉम लिखते हैं कि सूत्र <math>(x\lor x)</math> और <math> (\lnot x\lor\lnot x)</math> सुसंगत है यदि इस अनुमान नियम को निरंतर प्रयुक्त करने से दोनों खंड उत्पन्न नहीं हो सकते हैं , किसी भी <math> x</math>वेरिएबल के लिए. जैसा कि उन्होंने सिद्ध किया है, 2-सीएनएफ सूत्र तभी संतोषजनक है जब यह सुसंगत हो। क्योंकि, यदि कोई सूत्र सुसंगत नहीं है, तो दोनों खंडों को संतुष्ट करना संभव नहीं है <math> (x\lor x)</math> और <math>(\lnot x\lor\lnot x)</math> इसके साथ ही। और, यदि यह सुसंगत है, तो रूप के खंड को निरंतर जोड़कर सूत्र को बढ़ाया जा सकता है <math> (x\lor x)</math> या <math> (\lnot x\lor\lnot x)</math> समय में, प्रत्येक चरण में एकरूपता बनाए रखना, जब तक कि इसमें प्रत्येक वेरिएबल के लिए ऐसा खंड सम्मिलित न हो जाए। इन विस्तार चरणों में से प्रत्येक में, स्थिरता बनाए रखते हुए इन दो खंडों में से को सदैव जोड़ा जा सकता है, यदि नहीं तो अनुमान नियम का उपयोग करके अन्य खंड उत्पन्न किया जा सकता है। पुनः जब सभी वेरिएबल्स के सूत्र में इस रूप का खंड होता है, तो वेरिएबल सेट करके सभी <math> x</math> वेरिएबल्स का संतोषजनक असाइनमेंट उत्पन्न किया जा सकता है यदि सूत्र में खंड सम्मिलित है तो <math> (x\lor x)</math> सत्य है और यदि सूत्र में खंड सम्मिलित है तो इसे गलत पर सेट <math>(\lnot x\lor\lnot x)</math> करना होता है .<ref name="Krom1967"/> | ||
क्रॉम मुख्य रूप से एल्गोरिदम की दक्षता के अतिरिक्त अनुमान नियमों की प्रणालियों की [[पूर्णता (तर्क)]] से चिंतित था। चूँकि, उनकी पद्धति 2-संतोषजनकता समस्याओं को हल करने के लिए बहुपद समयबद्धता की ओर ले जाती है। समान वेरिएबल का उपयोग करने वाले सभी खंडों को साथ समूहित करके, और खंडों की प्रत्येक जोड़ी पर अनुमान नियम प्रयुक्त करके, किसी दिए गए 2-सीएनएफ उदाहरण से संभव सभी अनुमान | क्रॉम मुख्य रूप से एल्गोरिदम की दक्षता के अतिरिक्त अनुमान नियमों की प्रणालियों की [[पूर्णता (तर्क)]] से चिंतित था। चूँकि, उनकी पद्धति 2-संतोषजनकता समस्याओं को हल करने के लिए बहुपद समयबद्धता की ओर ले जाती है। समान वेरिएबल का उपयोग करने वाले सभी खंडों को साथ समूहित करके, और खंडों की प्रत्येक जोड़ी पर अनुमान नियम प्रयुक्त करके, किसी दिए गए 2-सीएनएफ उदाहरण से संभव सभी अनुमान खोजता संभव है, और यह परीक्षण करना संभव है कि क्या यह सुसंगत है, कुल समय में {{math|O(''n''<sup>3</sup>)}},है जहाँ {{math|''n''}} उदाहरण में वेरिएबलों की संख्या है। यह सूत्र वेरिएबलों की संख्या को गुणा करने से {{math|O(''n''<sup>2</sup>)}} प्राप्त होता है किसी दिए गए वेरिएबल को सम्मिलित करने वाले खंडों के जोड़े की संख्या, जिस पर अनुमान नियम प्रयुक्त किया जा सकता है। इस प्रकार, यह निर्धारित करना संभव है कि दिया गया 2-सीएनएफ उदाहरण समय में संतोषजनक या नहीं {{math|O(''n''<sup>3</sup>)}} है . क्योंकि क्रॉम की विधि का उपयोग करके संतोषजनक असाइनमेंट खोजने में अनुक्रम सम्मिलित होता है {{math|O(''n'')}} निरंतरता की जांच, इसमें समय लगेगा {{math|O(''n''<sup>4</sup>)}}. {{harvtxt|इवेन |इटाई|शमीर|1976}} तेज़ समय सीमा का उद्धरण दें {{math|O(''n''<sup>2</sup>)}} इस एल्गोरिथम के लिए, इसके संचालन के अधिक सावधानीपूर्वक क्रम पर आधारित है। फिर भी, पश्चात के रैखिक समय एल्गोरिदम द्वारा इस छोटी समय सीमा में भी अधिक सुधार {{harvtxt|इवेन |इटाई|शमीर|1976}} और {{harvtxt|एस्पवॉल|प्लास|टारजन|1979}} के द्वारा किया गया था | | ||
2-संतोषजनकता उदाहरण के निहितार्थ ग्राफ के संदर्भ में, क्रॉम के अनुमान नियम की व्याख्या ग्राफ के संक्रमणीय समापन के निर्माण के रूप में की जा सकती है। जैसा {{harvtxt|कुक |1971}} देखता है, इसे रिज़ॉल्यूशन (तर्क) के सिद्धांत का उपयोग करके संतुष्टि समस्याओं को हल करने के लिए डेविस-पुटनम एल्गोरिदम के उदाहरण के रूप में भी देखा जा सकता है। इसकी शुद्धता डेविस-पुटनम एल्गोरिथ्म की अधिक सामान्य शुद्धता से अनुसरण करती है। इसकी बहुपद समय सीमा इस तथ्य से उत्पन्न होती है कि प्रत्येक रिज़ॉल्यूशन चरण उदाहरण में खंडों की संख्या बढ़ाता है, जो कि वेरिएबल की संख्या के द्विघात फलन द्वारा ऊपरी सीमा पर होता है।<ref>{{citation|first=Stephen A.|last=Cook|author-link=Stephen Cook|contribution=The complexity of theorem-proving procedures|title=Proc. 3rd ACM Symp. Theory of Computing (STOC)|year=1971|pages=151–158|doi=10.1145/800157.805047|s2cid=7573663}}.</ref> | 2-संतोषजनकता उदाहरण के निहितार्थ ग्राफ के संदर्भ में, क्रॉम के अनुमान नियम की व्याख्या ग्राफ के संक्रमणीय समापन के निर्माण के रूप में की जा सकती है। जैसा {{harvtxt|कुक |1971}} देखता है, इसे रिज़ॉल्यूशन (तर्क) के सिद्धांत का उपयोग करके संतुष्टि समस्याओं को हल करने के लिए डेविस-पुटनम एल्गोरिदम के उदाहरण के रूप में भी देखा जा सकता है। इसकी शुद्धता डेविस-पुटनम एल्गोरिथ्म की अधिक सामान्य शुद्धता से अनुसरण करती है। इसकी बहुपद समय सीमा इस तथ्य से उत्पन्न होती है कि प्रत्येक रिज़ॉल्यूशन चरण उदाहरण में खंडों की संख्या बढ़ाता है, जो कि वेरिएबल की संख्या के द्विघात फलन द्वारा ऊपरी सीमा पर होता है।<ref>{{citation|first=Stephen A.|last=Cook|author-link=Stephen Cook|contribution=The complexity of theorem-proving procedures|title=Proc. 3rd ACM Symp. Theory of Computing (STOC)|year=1971|pages=151–158|doi=10.1145/800157.805047|s2cid=7573663}}.</ref> | ||
| Line 66: | Line 66: | ||
{{harvtxt|इवेन |इटाई|शमीर|1976}} [[बाइनरी डेटा]] और जोड़ीदार बाधाओं के साथ बाधा संतुष्टि समस्याओं को हल करने के लिए सीमित बैकट्रैकिंग से जुड़ी तकनीक का वर्णन करता है जहाँ वह इस तकनीक को कक्षा समय-निर्धारण की समस्या पर प्रयुक्त करते हैं, किन्तु वह यह भी देखते हैं कि यह 2-एसएटी सहित अन्य समस्याओं पर भी प्रयुक्त होती है।<ref name="EIS76">{{citation|first1=S.|last1=Even|author1-link=Shimon Even|first2=A.|last2=Itai|first3=A.|last3=Shamir|author3-link=Adi Shamir|title=On the complexity of time table and multi-commodity flow problems|journal=[[SIAM Journal on Computing]]|volume=5|issue=4|year=1976|pages=691–703|doi=10.1137/0205048}}.</ref> | {{harvtxt|इवेन |इटाई|शमीर|1976}} [[बाइनरी डेटा]] और जोड़ीदार बाधाओं के साथ बाधा संतुष्टि समस्याओं को हल करने के लिए सीमित बैकट्रैकिंग से जुड़ी तकनीक का वर्णन करता है जहाँ वह इस तकनीक को कक्षा समय-निर्धारण की समस्या पर प्रयुक्त करते हैं, किन्तु वह यह भी देखते हैं कि यह 2-एसएटी सहित अन्य समस्याओं पर भी प्रयुक्त होती है।<ref name="EIS76">{{citation|first1=S.|last1=Even|author1-link=Shimon Even|first2=A.|last2=Itai|first3=A.|last3=Shamir|author3-link=Adi Shamir|title=On the complexity of time table and multi-commodity flow problems|journal=[[SIAM Journal on Computing]]|volume=5|issue=4|year=1976|pages=691–703|doi=10.1137/0205048}}.</ref> | ||
उनके दृष्टिकोण का मूल विचार समय में वेरिएबल, आंशिक सत्य असाइनमेंट का निर्माण करना है। एल्गोरिदम के कुछ चरण चयन बिंदु हैं, ऐसे बिंदु जिन पर वेरिएबल को दो भिन्न -भिन्न सत्य मानों में से कोई दिया जा सकता है, और एल्गोरिदम के पश्चात के चरणों के कारण यह इन विकल्प बिंदुओं में से किसी पर पीछे जा सकता है। चूँकि , केवल सबसे | उनके दृष्टिकोण का मूल विचार समय में वेरिएबल, आंशिक सत्य असाइनमेंट का निर्माण करना है। एल्गोरिदम के कुछ चरण चयन बिंदु हैं, ऐसे बिंदु जिन पर वेरिएबल को दो भिन्न -भिन्न सत्य मानों में से कोई दिया जा सकता है, और एल्गोरिदम के पश्चात के चरणों के कारण यह इन विकल्प बिंदुओं में से किसी पर पीछे जा सकता है। चूँकि , केवल सबसे आधुनिक विकल्प को ही वापस लिया जा सकता है। नवीनतम से पहले किए गए सभी विकल्प स्थायी हैं।<ref name="EIS76" /> | ||
प्रारंभ में, कोई विकल्प बिंदु नहीं है, और सभी वेरिएबल अनअसाइन किए गए हैं। प्रत्येक चरण में, एल्गोरिदम उस वेरिएबल को चुनता है जिसका मान सेट करना है, इस प्रकार: | प्रारंभ में, कोई विकल्प बिंदु नहीं है, और सभी वेरिएबल अनअसाइन किए गए हैं। प्रत्येक चरण में, एल्गोरिदम उस वेरिएबल को चुनता है जिसका मान सेट करना है, इस प्रकार: | ||
*यदि कोई ऐसा खंड है जिसके दोनों वेरिएबल पहले से ही सेट हैं, इस तरह से जो खंड को गलत | *यदि कोई ऐसा खंड है जिसके दोनों वेरिएबल पहले से ही सेट हैं, इस तरह से जो खंड को गलत सिद्ध करता है, तो एल्गोरिदम अपने सबसे हालिया विकल्प बिंदु पर वापस आ जाता है, उस विकल्प के पश्चात से किए गए असाइनमेंट को पूर्ववत कर देता है, और उस विकल्प पर किए गए निर्णय को विपरीत देता है। यदि कोई विकल्प बिंदु नहीं है, या यदि एल्गोरिदम पहले से ही सबसे हालिया विकल्प बिंदु पर पीछे हट गया है, तो यह खोज को रोक देता है और रिपोर्ट करता है कि इनपुट 2-सीएनएफ सूत्र असंतोषजनक है। | ||
*यदि कोई ऐसा खंड है जिसमें खंड के दो वेरिएबलों में से पहले ही सेट किया जा चुका है, और खंड अभी भी या तो सत्य या गलत हो सकता है, तो दूसरा वेरिएबल इस तरह से सेट किया जाता है जो खंड को सत्य बनने के लिए विवश करता है। | *यदि कोई ऐसा खंड है जिसमें खंड के दो वेरिएबलों में से पहले ही सेट किया जा चुका है, और खंड अभी भी या तो सत्य या गलत हो सकता है, तो दूसरा वेरिएबल इस तरह से सेट किया जाता है जो खंड को सत्य बनने के लिए विवश करता है। | ||
*शेष स्तिथि में, प्रत्येक खंड के या तो सत्य होने की | *शेष स्तिथि में, प्रत्येक खंड के या तो सत्य होने की आश्वासन है, चाहे शेष वेरिएबल कैसे भी निर्दिष्ट किए गए हों, या इसके दो वेरिएबल में से किसी को भी अभी तक निर्दिष्ट नहीं किया गया है। इस स्तिथि में एल्गोरिदम नया विकल्प बिंदु बनाता है और किसी भी अनअसाइन किए गए वेरिएबल को इच्छानुसार चुने गए मान पर सेट करता है। | ||
सहज रूप से, एल्गोरिथ्म अपने प्रत्येक विकल्प को चुनने के पश्चात अनुमान की सभी श्रृंखलाओं का पालन करता है। इससे या तो विरोधाभास | सहज रूप से, एल्गोरिथ्म अपने प्रत्येक विकल्प को चुनने के पश्चात अनुमान की सभी श्रृंखलाओं का पालन करता है। इससे या तो विरोधाभास उत्पन्न होता है और कदम पीछे हट जाता है, या, यदि कोई विरोधाभास नहीं निकलता है, तो इसका अर्थ यह है कि चुनाव सही था जो संतोषजनक असाइनमेंट की ओर ले जाता है। इसलिए, एल्गोरिदम या तो सही रूप से संतोषजनक असाइनमेंट पाता है या यह सही रूप से निर्धारित करता है कि इनपुट असंतोषजनक है।<ref name="EIS76" /> | ||
यहां तक कि एट अल. इस एल्गोरिथम को कुशलतापूर्वक कैसे कार्यान्वित किया जाए, इसका विस्तार से वर्णन नहीं किया गया। वह केवल यह बताते हैं कि किसी भी निर्णय के निहितार्थ खोजने के लिए उपयुक्त डेटा संरचनाओं का उपयोग करके, एल्गोरिदम के प्रत्येक चरण (बैकट्रैकिंग के अतिरिक्त ) को जल्दी से निष्पादित किया जा सकता है। चूँकि | यहां तक कि एट अल. इस एल्गोरिथम को कुशलतापूर्वक कैसे कार्यान्वित किया जाए, इसका विस्तार से वर्णन नहीं किया गया। वह केवल यह बताते हैं कि किसी भी निर्णय के निहितार्थ खोजने के लिए उपयुक्त डेटा संरचनाओं का उपयोग करके, एल्गोरिदम के प्रत्येक चरण (बैकट्रैकिंग के अतिरिक्त ) को जल्दी से निष्पादित किया जा सकता है। चूँकि कुछ इनपुट के कारण एल्गोरिदम अनेक बार बैकट्रैक कर सकता है, हर बार बैकट्रैकिंग से पहले अनेक चरण निष्पादित करता है, इसलिए इसकी समग्र सम्मिश्र ता अरेखीय हो सकती है। इस समस्या से बचने के लिए, वह एल्गोरिदम को संशोधित करते हैं जिससे , प्रत्येक विकल्प बिंदु पर पहुंचने के पश्चात, यह विकल्प बिंदु पर वेरिएबल सेट के लिए दो असाइनमेंट का साथ परीक्षण करना प्रारंभ कर दे, दोनों असाइनमेंट में से प्रत्येक पर समान संख्या में चरण खर्च करें। जैसे ही इन दो असाइनमेंट में से का परीक्षण और विकल्प बिंदु बनाता है, दूसरा परीक्षण रोक दिया जाता है, जिससे एल्गोरिदम के किसी भी चरण में बैकट्रैकिंग ट्री की केवल दो शाखाएं हों जिनका अभी भी परीक्षण किया जा रहा हो। इस प्रकार, किसी भी वेरिएबल के लिए दो परीक्षण करने में बिताया गया कुल समय इनपुट सूत्र के उन वेरिएबलों और खंडों की संख्या के समानुपाती होता है जिनके मान स्थायी रूप से निर्दिष्ट होते हैं। परिणामस्वरूप, एल्गोरिथ्म कुल मिलाकर रैखिक समय लेता है।<ref name="EIS76" /> | ||
=== | ===शक्ति से जुड़े अवयव === | ||
{{harvtxt|एस्पवॉल|प्लास|टारजन|1979}} ग्राफ़ सिद्धांत से दृढ़ता से जुड़े अवयवों की धारणा के आधार पर, 2-संतोषजनक उदाहरणों को हल करने के लिए सरल रैखिक समय प्रक्रिया | {{harvtxt|एस्पवॉल|प्लास|टारजन|1979}} ग्राफ़ सिद्धांत से दृढ़ता से जुड़े अवयवों की धारणा के आधार पर, 2-संतोषजनक उदाहरणों को हल करने के लिए सरल रैखिक समय प्रक्रिया मिली थी।<ref name="APT79"/> | ||
निर्देशित ग्राफ़ में दो शीर्षों को एक-दूसरे से | निर्देशित ग्राफ़ में दो शीर्षों को एक-दूसरे से शक्ति से जुड़ा हुआ माना जाता है यदि से दूसरे तक कोई निर्देशित पथ हो और इसके विपरीत। यह तुल्यता संबंध है, और ग्राफ़ के शीर्षों को दृढ़ता से जुड़े अवयवों , उपसमुच्चयों में विभाजित किया जा सकता है जिनके अंदर प्रत्येक दो शीर्ष दृढ़ता से जुड़े हुए हैं। [[गहराई-पहली खोज|डेप्थ -फर्स्ट सर्च]] के आधार पर ग्राफ़ के दृढ़ता से जुड़े अवयवों को खोजने के लिए अनेक कुशल रैखिक समय एल्गोरिदम हैं: टार्जन के दृढ़ता से जुड़े अवयव एल्गोरिदम<ref>{{citation|first=Robert E.|last=Tarjan|author-link=Robert Tarjan|title=Depth-first search and linear graph algorithms|journal=[[SIAM Journal on Computing]]|volume=1|year=1972|issue=2|pages=146–160|doi=10.1137/0201010|s2cid=16467262 }}.</ref> और [[पथ-आधारित मजबूत घटक एल्गोरिदम|पथ-आधारित शक्तिशाली अवयव एल्गोरिदम]]<ref>First published by {{citation | ||
| last1 = Cheriyan | first1 = J. | | last1 = Cheriyan | first1 = J. | ||
| last2 = Mehlhorn | first2 = K. | author2-link = Kurt Mehlhorn | | last2 = Mehlhorn | first2 = K. | author2-link = Kurt Mehlhorn | ||
| Line 102: | Line 102: | ||
| year = 2003}}.</ref> प्रत्येक एकल गहराई-पहली खोज करता है। कोसाराजू का एल्गोरिदम दो गहराई-पहली खोज करता है, किन्तु यह बहुत सरल है। | | year = 2003}}.</ref> प्रत्येक एकल गहराई-पहली खोज करता है। कोसाराजू का एल्गोरिदम दो गहराई-पहली खोज करता है, किन्तु यह बहुत सरल है। | ||
निहितार्थ ग्राफ के संदर्भ में, जब भी शाब्दिक से दूसरे और इसके विपरीत निहितार्थ की श्रृंखला उपस्तिथ होती है, तो दो शाब्दिक ही दृढ़ता से जुड़े अवयव से संबंधित होते हैं। इसलिए, दिए गए 2-संतोषजनकता उदाहरण के लिए किसी भी संतोषजनक असाइनमेंट में दो शाब्दिकों का समान मान होना चाहिए। विशेष रूप से, यदि वेरिएबल और उसका निषेध दोनों ही | निहितार्थ ग्राफ के संदर्भ में, जब भी शाब्दिक से दूसरे और इसके विपरीत निहितार्थ की श्रृंखला उपस्तिथ होती है, तो दो शाब्दिक ही दृढ़ता से जुड़े अवयव से संबंधित होते हैं। इसलिए, दिए गए 2-संतोषजनकता उदाहरण के लिए किसी भी संतोषजनक असाइनमेंट में दो शाब्दिकों का समान मान होना चाहिए। विशेष रूप से, यदि वेरिएबल और उसका निषेध दोनों ही शक्ति से जुड़े अवयव से संबंधित हैं, तो उदाहरण को संतुष्ट नहीं किया जा सकता है, क्योंकि इन दोनों शाब्दिकों को समान मान निर्दिष्ट करना असंभव है। एस्पवॉल एट अल के रूप में दिखाया गया है, यह आवश्यक और पर्याप्त नियम है: 2-सीएनएफ सूत्र तभी संतोषजनक है जब कोई ऐसा वेरिएबल न हो जो इसके निषेध के समान शक्ति से जुड़े अवयव से संबंधित हो जाते है ।<ref name="APT79"/> | ||
यह तुरंत 2-सीएनएफ सूत्रों की संतुष्टि के परीक्षण के लिए रैखिक समय एल्गोरिदम की ओर ले जाता है: बस निहितार्थ ग्राफ पर शक्तिशाली कनेक्टिविटी विश्लेषण करें और जांचें कि प्रत्येक वेरिएबल और उसका निषेध भिन्न -भिन्न अवयवों से संबंधित है। चूँकि , एस्पवॉल एट अल के रूप | यह तुरंत 2-सीएनएफ सूत्रों की संतुष्टि के परीक्षण के लिए रैखिक समय एल्गोरिदम की ओर ले जाता है: बस निहितार्थ ग्राफ पर शक्तिशाली कनेक्टिविटी विश्लेषण करें और जांचें कि प्रत्येक वेरिएबल और उसका निषेध भिन्न -भिन्न अवयवों से संबंधित है। चूँकि , एस्पवॉल एट अल के रूप में यह भी दिखाया गया है, यह संतोषजनक असाइनमेंट खोजने के लिए रैखिक समय एल्गोरिदम की ओर भी ले जाता है, जब कोई उपस्तिथ होता है। उनका एल्गोरिदम निम्नलिखित चरण निष्पादित करता है: | ||
*उदाहरण के निहितार्थ ग्राफ का निर्माण करें, और शक्तिशाली कनेक्टिविटी विश्लेषण के लिए किसी भी ज्ञात रैखिक-समय एल्गोरिदम का उपयोग करके इसके दृढ़ता से जुड़े अवयवों को | *उदाहरण के निहितार्थ ग्राफ का निर्माण करें, और शक्तिशाली कनेक्टिविटी विश्लेषण के लिए किसी भी ज्ञात रैखिक-समय एल्गोरिदम का उपयोग करके इसके दृढ़ता से जुड़े अवयवों को खोजा जाता है । | ||
*जांचें कि क्या किसी दृढ़ता से जुड़े अवयव में वेरिएबल और उसका निषेध दोनों सम्मिलित हैं। यदि हां, तो रिपोर्ट करें कि स्तिथि संतोषजनक नहीं है और | *जांचें कि क्या किसी दृढ़ता से जुड़े अवयव में वेरिएबल और उसका निषेध दोनों सम्मिलित हैं। यदि हां, तो रिपोर्ट करें कि स्तिथि संतोषजनक नहीं है और रुकें है । | ||
*निहितार्थ ग्राफ के | *निहितार्थ ग्राफ के शक्ति से जुड़े अवयव का निर्माण करें, छोटा ग्राफ जिसमें प्रत्येक शक्ति से जुड़े अवयव के लिए शीर्ष और अवयव से किनारा हो {{math|''i''}} अवयव के लिए {{math|''j''}} जब भी निहितार्थ ग्राफ़ में कोई किनारा होता है {{math|''uv''}} ऐसा है कि {{math|''u''}} अवयव से संबंधित है {{math|''i''}} और {{math|''v''}} अवयव {{math|''j''}} से संबंधित है . संक्षेपण स्वचालित रूप से निर्देशित चक्रीय ग्राफ है और, निहितार्थ ग्राफ की तरह, जिससे इसे बनाया गया था, यह विषम -सममित ग्राफ है| विषम -सममित है। | ||
*संक्षेपण के शीर्षों को [[टोपोलॉजिकल छँटाई]] | *संक्षेपण के शीर्षों को [[टोपोलॉजिकल छँटाई|टोपोलॉजिकल सोर्टिंग]] करना है वास्तव में इसे पिछले चरण के साइड इफेक्ट के रूप में कुशलतापूर्वक प्राप्त किया जा सकता है, क्योंकि अवयव कोसाराजू के एल्गोरिदम द्वारा टोपोलॉजिकल क्रम में और टारजन के एल्गोरिदम द्वारा रिवर्स टोपोलॉजिकल क्रम में उत्पन्न होते हैं।<ref>{{citation|last=Harrison|first=Paul|title=Robust topological sorting and Tarjan's algorithm in Python|url=http://www.logarithmic.net/pfh/blog/01208083168|access-date=9 February 2011}}</ref> | ||
*रिवर्स टोपोलॉजिकल ऑर्डर में प्रत्येक अवयव के लिए, यदि इसके वेरिएबल में पहले से ही सत्य असाइनमेंट नहीं हैं, तो अवयव में सभी शाब्दिक को सत्य पर सेट करें। इसके कारण पूरक अवयव के सभी अक्षर गलत पर सेट हो जाते हैं। | *रिवर्स टोपोलॉजिकल ऑर्डर में प्रत्येक अवयव के लिए, यदि इसके वेरिएबल में पहले से ही सत्य असाइनमेंट नहीं हैं, तो अवयव में सभी शाब्दिक को सत्य पर सेट करें। इसके कारण पूरक अवयव के सभी अक्षर गलत पर सेट हो जाते हैं। | ||
रिवर्स टोपोलॉजिकल ऑर्डरिंग और तिरछी-समरूपता के कारण, जब शाब्दिक को सत्य पर सेट किया जाता है, तो निहितार्थों की श्रृंखला के माध्यम से इससे प्राप्त होने वाले सभी शाब्दिक पहले | |||