2-संतोषजनकता: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| 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>. जैसा कि उन्होंने साबित किया है, 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\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-सीएनएफ उदाहरण से संभव सभी अनुमान ढूंढना संभव है, और यह परीक्षण करना संभव है कि क्या यह सुसंगत है, कुल समय में {{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-संतुष्टि समस्याओं को हल करने के लिए बहुपद समयबद्धता की ओर ले जाती है। समान वेरिएबल का उपयोग करने वाले सभी खंडों को साथ समूहित करके, और खंडों की प्रत्येक जोड़ी पर अनुमान नियम प्रयुक्त करके, किसी दिए गए 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}}. | ||
| Line 71: | Line 71: | ||
*यदि कोई ऐसा खंड है जिसके दोनों वेरिएबल पहले से ही सेट हैं, इस तरह से जो खंड को गलत साबित करता है, तो एल्गोरिदम अपने सबसे हालिया विकल्प बिंदु पर वापस आ जाता है, उस विकल्प के पश्चात से किए गए असाइनमेंट को पूर्ववत कर देता है, और उस विकल्प पर किए गए निर्णय को उलट देता है। यदि कोई विकल्प बिंदु नहीं है, या यदि एल्गोरिदम पहले से ही सबसे हालिया विकल्प बिंदु पर पीछे हट गया है, तो यह खोज को रोक देता है और रिपोर्ट करता है कि इनपुट 2-सीएनएफ फॉर्मूला असंतोषजनक है। | *यदि कोई ऐसा खंड है जिसके दोनों वेरिएबल पहले से ही सेट हैं, इस तरह से जो खंड को गलत साबित करता है, तो एल्गोरिदम अपने सबसे हालिया विकल्प बिंदु पर वापस आ जाता है, उस विकल्प के पश्चात से किए गए असाइनमेंट को पूर्ववत कर देता है, और उस विकल्प पर किए गए निर्णय को उलट देता है। यदि कोई विकल्प बिंदु नहीं है, या यदि एल्गोरिदम पहले से ही सबसे हालिया विकल्प बिंदु पर पीछे हट गया है, तो यह खोज को रोक देता है और रिपोर्ट करता है कि इनपुट 2-सीएनएफ फॉर्मूला असंतोषजनक है। | ||
*यदि कोई ऐसा खंड है जिसमें खंड के दो वेरिएबलों में से पहले ही सेट किया जा चुका है, और खंड अभी भी या तो सत्य या गलत हो सकता है, तो दूसरा वेरिएबल इस तरह से सेट किया जाता है जो खंड को सत्य बनने के लिए मजबूर करता है। | *यदि कोई ऐसा खंड है जिसमें खंड के दो वेरिएबलों में से पहले ही सेट किया जा चुका है, और खंड अभी भी या तो सत्य या गलत हो सकता है, तो दूसरा वेरिएबल इस तरह से सेट किया जाता है जो खंड को सत्य बनने के लिए मजबूर करता है। | ||
*शेष | *शेष स्तिथि में, प्रत्येक खंड के या तो सत्य होने की गारंटी है, चाहे शेष वेरिएबल कैसे भी निर्दिष्ट किए गए हों, या इसके दो वेरिएबल में से किसी को भी अभी तक निर्दिष्ट नहीं किया गया है। इस स्तिथि में एल्गोरिदम नया विकल्प बिंदु बनाता है और किसी भी अनअसाइन किए गए वेरिएबल को मनमाने ढंग से चुने गए मान पर सेट करता है। | ||
सहज रूप से, एल्गोरिथ्म अपने प्रत्येक विकल्प को चुनने के पश्चात अनुमान की सभी श्रृंखलाओं का पालन करता है। इससे या तो विरोधाभास पैदा होता है और कदम पीछे हट जाता है, या, यदि कोई विरोधाभास नहीं निकलता है, तो इसका | सहज रूप से, एल्गोरिथ्म अपने प्रत्येक विकल्प को चुनने के पश्चात अनुमान की सभी श्रृंखलाओं का पालन करता है। इससे या तो विरोधाभास पैदा होता है और कदम पीछे हट जाता है, या, यदि कोई विरोधाभास नहीं निकलता है, तो इसका अर्थ यह है कि चुनाव सही था जो संतोषजनक असाइनमेंट की ओर ले जाता है। इसलिए, एल्गोरिदम या तो सही ढंग से संतोषजनक असाइनमेंट पाता है या यह सही ढंग से निर्धारित करता है कि इनपुट असंतोषजनक है।<ref name="EIS76" /> | ||
यहां तक कि एट अल. इस एल्गोरिथम को कुशलतापूर्वक कैसे कार्यान्वित किया जाए, इसका विस्तार से वर्णन नहीं किया गया। वे केवल यह बताते हैं कि किसी भी निर्णय के निहितार्थ खोजने के लिए उपयुक्त डेटा संरचनाओं का उपयोग करके, एल्गोरिदम के प्रत्येक चरण (बैकट्रैकिंग के | यहां तक कि एट अल. इस एल्गोरिथम को कुशलतापूर्वक कैसे कार्यान्वित किया जाए, इसका विस्तार से वर्णन नहीं किया गया। वे केवल यह बताते हैं कि किसी भी निर्णय के निहितार्थ खोजने के लिए उपयुक्त डेटा संरचनाओं का उपयोग करके, एल्गोरिदम के प्रत्येक चरण (बैकट्रैकिंग के अतिरिक्त ) को जल्दी से निष्पादित किया जा सकता है। चूँकि , कुछ इनपुट के कारण एल्गोरिदम अनेक बार बैकट्रैक कर सकता है, हर बार बैकट्रैकिंग से पहले अनेक चरण निष्पादित करता है, इसलिए इसकी समग्र सम्मिश्र ता अरेखीय हो सकती है। इस समस्या से बचने के लिए, वे एल्गोरिदम को संशोधित करते हैं जिससे , प्रत्येक विकल्प बिंदु पर पहुंचने के पश्चात, यह विकल्प बिंदु पर वेरिएबल सेट के लिए दो असाइनमेंट का साथ परीक्षण करना शुरू कर दे, दोनों असाइनमेंट में से प्रत्येक पर समान संख्या में चरण खर्च करें। जैसे ही इन दो असाइनमेंट में से का परीक्षण और विकल्प बिंदु बनाता है, दूसरा परीक्षण रोक दिया जाता है, जिससे एल्गोरिदम के किसी भी चरण में बैकट्रैकिंग ट्री की केवल दो शाखाएं हों जिनका अभी भी परीक्षण किया जा रहा हो। इस प्रकार, किसी भी वेरिएबल के लिए दो परीक्षण करने में बिताया गया कुल समय इनपुट सूत्र के उन वेरिएबलों और खंडों की संख्या के समानुपाती होता है जिनके मान स्थायी रूप से निर्दिष्ट होते हैं। परिणामस्वरूप, एल्गोरिथ्म कुल मिलाकर रैखिक समय लेता है।<ref name="EIS76" /> | ||
| Line 82: | Line 82: | ||
{{harvtxt|एस्पवॉल|प्लास|टारजन|1979}} ग्राफ़ सिद्धांत से दृढ़ता से जुड़े अवयवों की धारणा के आधार पर, 2-संतोषजनक उदाहरणों को हल करने के लिए सरल रैखिक समय प्रक्रिया मिली।<ref name="APT79"/> | {{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-सीएनएफ फॉर्मूला तभी संतोषजनक है जब कोई ऐसा वेरिएबल न हो जो इसके निषेध के समान मजबूती से जुड़े घटक से संबंधित हो।<ref name="APT79"/> | ||
यह तुरंत 2-सीएनएफ सूत्रों की संतुष्टि के परीक्षण के लिए रैखिक समय एल्गोरिदम की ओर ले जाता है: बस निहितार्थ ग्राफ पर मजबूत कनेक्टिविटी विश्लेषण करें और जांचें कि प्रत्येक वेरिएबल और उसका निषेध अलग-अलग अवयवों से संबंधित है। चूँकि , एस्पवॉल एट अल के रूप में। यह भी दिखाया गया है, यह संतोषजनक असाइनमेंट खोजने के लिए रैखिक समय एल्गोरिदम की ओर भी ले जाता है, जब कोई | यह तुरंत 2-सीएनएफ सूत्रों की संतुष्टि के परीक्षण के लिए रैखिक समय एल्गोरिदम की ओर ले जाता है: बस निहितार्थ ग्राफ पर मजबूत कनेक्टिविटी विश्लेषण करें और जांचें कि प्रत्येक वेरिएबल और उसका निषेध अलग-अलग अवयवों से संबंधित है। चूँकि , एस्पवॉल एट अल के रूप में। यह भी दिखाया गया है, यह संतोषजनक असाइनमेंट खोजने के लिए रैखिक समय एल्गोरिदम की ओर भी ले जाता है, जब कोई उपस्तिथ होता है। उनका एल्गोरिदम निम्नलिखित चरण निष्पादित करता है: | ||
*उदाहरण के निहितार्थ ग्राफ का निर्माण करें, और मजबूत कनेक्टिविटी विश्लेषण के लिए किसी भी ज्ञात रैखिक-समय एल्गोरिदम का उपयोग करके इसके दृढ़ता से जुड़े अवयवों को ढूंढें। | *उदाहरण के निहितार्थ ग्राफ का निर्माण करें, और मजबूत कनेक्टिविटी विश्लेषण के लिए किसी भी ज्ञात रैखिक-समय एल्गोरिदम का उपयोग करके इसके दृढ़ता से जुड़े अवयवों को ढूंढें। | ||
*जांचें कि क्या किसी दृढ़ता से जुड़े घटक में वेरिएबल और उसका निषेध दोनों सम्मिलित हैं। यदि हां, तो रिपोर्ट करें कि स्तिथि संतोषजनक नहीं है और रुकें। | *जांचें कि क्या किसी दृढ़ता से जुड़े घटक में वेरिएबल और उसका निषेध दोनों सम्मिलित हैं। यदि हां, तो रिपोर्ट करें कि स्तिथि संतोषजनक नहीं है और रुकें। | ||
| Line 119: | Line 119: | ||
===ज्यामितीय वस्तुओं का संघर्ष-मुक्त स्थान === | ===ज्यामितीय वस्तुओं का संघर्ष-मुक्त स्थान === | ||
[[स्वचालित लेबल प्लेसमेंट]] समस्या के लिए अनेक | [[स्वचालित लेबल प्लेसमेंट]] समस्या के लिए अनेक स्पष्ट और अनुमानित एल्गोरिदम 2-संतुष्टि पर आधारित हैं। यह समस्या किसी आरेख या मानचित्र की विशेषताओं पर पाठ्य लेबल लगाने से संबंधित है। सामान्यतः , प्रत्येक लेबल के लिए संभावित स्थानों का सेट अत्यधिक प्रतिबंधित होता है, न केवल मानचित्र द्वारा (प्रत्येक लेबल को उस सुविधा के पास होना चाहिए जिसे वह लेबल करता है, और अन्य सुविधाओं को अस्पष्ट नहीं करना चाहिए), किन्तु एक-दूसरे द्वारा: प्रत्येक दो लेबल को एक-दूसरे को ओवरलैप करने से बचना चाहिए, अन्यथा वे अस्पष्ट हो जाएंगे। सामान्यतः र, इन बाधाओं का पालन करने वाला लेबल प्लेसमेंट ढूंढना [[ एनपी कठिन |एनपी कठिन]] समस्या है। चूँकि , यदि प्रत्येक फीवेरिएबल में उसके लेबल के लिए केवल दो संभावित स्थान हैं (जैसे, फीवेरिएबल के बाईं और दाईं ओर विस्तार) तो लेबल प्लेसमेंट को बहुपद समय में हल किया जा सकता है। इस स्तिथि में, कोई 2-संतोषजनक उदाहरण बना सकता है जिसमें प्रत्येक लेबल के लिए वेरिएबल होता है और जिसमें लेबल की प्रत्येक जोड़ी के लिए खंड होता है जो ओवरलैप हो सकता है, जिससे उन्हें ओवरलैपिंग स्थिति आवंटित करने से रोका जा सकता है। यदि लेबल सभी सर्वांगसम आयत हैं, तो संबंधित 2-संतुष्टि उदाहरण को केवल रैखिक रूप से अनेक बाधाओं के रूप में दिखाया जा सकता है, जिससे लेबलिंग खोजने के लिए निकट-रेखीय समय एल्गोरिदम हो सकता है।<ref name="fw91">{{citation|first1=M.|last1=Formann|first2=F.|last2=Wagner|contribution=A packing problem with applications to lettering of maps|title=Proc. 7th ACM Symposium on Computational Geometry|year=1991|pages=281–288|doi=10.1145/109648.109680|isbn=978-0-89791-426-0|title-link=Symposium on Computational Geometry|s2cid=15740667}}.</ref> {{harvtxt|पून|झू |चिन|1998}} मानचित्र लेबलिंग समस्या का वर्णन करें जिसमें प्रत्येक लेबल आयत है जिसे लेबल किए गए रेखा खंड के संबंध में तीन स्थितियों में से में रखा जा सकता है: इसमें खंड इसके किनारों में से के रूप में हो सकता है, या यह खंड पर केंद्रित हो सकता है। वे दो बाइनरी वेरिएबल का उपयोग करके इन तीन स्थितियों का प्रतिनिधित्व इस तरह से करते हैं कि, फिर से, वैध लेबलिंग के अस्तित्व का परीक्षण करना 2-संतुष्टि समस्या बन जाता है।<ref>{{citation|first1=Chung Keung|last1=Poon|first2=Binhai|last2=Zhu|first3=Francis|last3=Chin|author3-link=Y. L. Chin|title=A polynomial time solution for labeling a rectilinear map|journal=[[Information Processing Letters]]|volume=65|issue=4|year=1998|pages=201–207|doi=10.1016/S0020-0190(98)00002-7}}.</ref> | ||
{{harvtxt|फॉर्मैन |वैगनर|1991}} किसी दिए गए बिंदुओं के सेट के लिए सबसे बड़े संभावित आकार के वर्ग लेबल खोजने की समस्या के लिए सन्निकटन एल्गोरिदम के भाग के रूप में 2-संतुष्टि का उपयोग करें, इस बाधा के साथ कि प्रत्येक लेबल का कोना उस बिंदु पर हो जिस बिंदु पर वह लेबल करता है। किसी दिए गए आकार के साथ लेबलिंग खोजने के लिए, वे उन वर्गों को हटा देते हैं, जिन्हें यदि दोगुना किया जाए, तो वे दूसरे बिंदु को ओवरलैप कर देंगे, और वे उन बिंदुओं को हटा देते हैं, जिन्हें इस तरह से लेबल किया जा सकता है कि संभवतः किसी अन्य बिंदु के लेबल के साथ ओवरलैप नहीं किया जा सकता है। वे दिखाते हैं कि इन उन्मूलन नियमों के कारण शेष बिंदुओं पर प्रति बिंदु केवल दो संभावित लेबल प्लेसमेंट होते हैं, जिससे 2-संतुष्टि उदाहरण के समाधान के रूप में वैध लेबल प्लेसमेंट (यदि कोई | {{harvtxt|फॉर्मैन |वैगनर|1991}} किसी दिए गए बिंदुओं के सेट के लिए सबसे बड़े संभावित आकार के वर्ग लेबल खोजने की समस्या के लिए सन्निकटन एल्गोरिदम के भाग के रूप में 2-संतुष्टि का उपयोग करें, इस बाधा के साथ कि प्रत्येक लेबल का कोना उस बिंदु पर हो जिस बिंदु पर वह लेबल करता है। किसी दिए गए आकार के साथ लेबलिंग खोजने के लिए, वे उन वर्गों को हटा देते हैं, जिन्हें यदि दोगुना किया जाए, तो वे दूसरे बिंदु को ओवरलैप कर देंगे, और वे उन बिंदुओं को हटा देते हैं, जिन्हें इस तरह से लेबल किया जा सकता है कि संभवतः किसी अन्य बिंदु के लेबल के साथ ओवरलैप नहीं किया जा सकता है। वे दिखाते हैं कि इन उन्मूलन नियमों के कारण शेष बिंदुओं पर प्रति बिंदु केवल दो संभावित लेबल प्लेसमेंट होते हैं, जिससे 2-संतुष्टि उदाहरण के समाधान के रूप में वैध लेबल प्लेसमेंट (यदि कोई उपस्तिथ है) पाया जा सकता है। सबसे बड़े लेबल आकार की खोज करके जो हल करने योग्य 2-संतोषजनक उदाहरण की ओर ले जाता है, उन्हें वैध लेबल प्लेसमेंट मिलता है जिसके लेबल अधिकतम समाधान से कम से कम आधे बड़े होते हैं। अर्थात्, उनके एल्गोरिथ्म का [[सन्निकटन अनुपात]] अधिकतम दो है।<ref name="fw91"/><ref>{{citation|first1=Frank|last1=Wagner|first2=Alexander|last2=Wolff|title=A practical map labeling algorithm|journal=[[Computational Geometry (journal)|Computational Geometry: Theory and Applications]]|volume=7|issue=5–6|year=1997|pages=387–404|doi=10.1016/S0925-7721(96)00007-7}}.</ref> इसी तरह, यदि प्रत्येक लेबल आयताकार है और उसे इस तरह से रखा जाना चाहिए कि जिस बिंदु पर वह लेबल करता है वह उसके निचले किनारे के साथ कहीं है, तो सबसे बड़े लेबल आकार को खोजने के लिए 2-संतुष्टि का उपयोग करें जिसके लिए समाधान है जिसमें प्रत्येक लेबल के निचले कोने पर बिंदु होता है जिससे अधिकतम दो का अनुमान अनुपात होता है।<ref>{{citation|first1=Srinivas|last1=Doddi|first2=Madhav V.|last2=Marathe|first3=Andy|last3=Mirzaian|first4=Bernard M. E.|last4=Moret|first5=Binhai|last5=Zhu|contribution=Map labeling and its generalizations|title=Proc. 8th ACM-SIAM Symp. Discrete Algorithms (SODA)|year=1997|pages=148–157|url=http://portal.acm.org/citation.cfm?id=314250|isbn=9780898713909|series=Soda '97}}.</ref> | ||
अन्य ज्यामितीय प्लेसमेंट समस्याओं के लिए 2-संतुष्टि के समान अनुप्रयोग किए गए हैं। [[ग्राफ ड्राइंग]] में, यदि शीर्ष स्थान तय किए गए हैं और प्रत्येक किनारे को दो संभावित स्थानों में से के साथ गोलाकार चाप के रूप में खींचा जाना चाहिए (उदाहरण के लिए आर्क आरेख के रूप में), तो क्रॉसिंग से बचने के लिए प्रत्येक किनारे के लिए कौन सा चाप का उपयोग करना है यह चुनने की समस्या प्रत्येक किनारे के लिए वेरिएबल के साथ 2-संतुष्टि की समस्या है और प्लेसमेंट की प्रत्येक जोड़ी के लिए बाधा है जो क्रॉसिंग की ओर ले जाएगी। चूँकि , इस | अन्य ज्यामितीय प्लेसमेंट समस्याओं के लिए 2-संतुष्टि के समान अनुप्रयोग किए गए हैं। [[ग्राफ ड्राइंग]] में, यदि शीर्ष स्थान तय किए गए हैं और प्रत्येक किनारे को दो संभावित स्थानों में से के साथ गोलाकार चाप के रूप में खींचा जाना चाहिए (उदाहरण के लिए आर्क आरेख के रूप में), तो क्रॉसिंग से बचने के लिए प्रत्येक किनारे के लिए कौन सा चाप का उपयोग करना है यह चुनने की समस्या प्रत्येक किनारे के लिए वेरिएबल के साथ 2-संतुष्टि की समस्या है और प्लेसमेंट की प्रत्येक जोड़ी के लिए बाधा है जो क्रॉसिंग की ओर ले जाएगी। चूँकि , इस स्तिथि में समाधान को गति देना संभव है, एल्गोरिदम की तुलना में जो ग्राफ़ के [[अंतर्निहित ग्राफ]] को खोजकर, निहितार्थ ग्राफ़ का स्पष्ट प्रतिनिधित्व बनाता है और फिर खोजता है।<ref>{{citation|first1=Alon|last1=Efrat|first2=Cesim|last2=Erten|first3=Stephen G.|last3=Kobourov|title=Fixed-location circular arc drawing of planar graphs|journal=[[Journal of Graph Algorithms and Applications]]|volume=11|issue=1|pages=145–164|year=2007|url=http://jgaa.info/accepted/2007/EfratErtenKobourov2007.11.1.pdf|doi=10.7155/jgaa.00140}}.</ref> [[वीएलएसआई]] एकीकृत परिपथ डिजाइन में, यदि मॉड्यूल का संग्रह तारों से जुड़ा होना चाहिए जो प्रत्येक अधिकतम बार झुक सकता है, तो तारों के लिए फिर से दो संभावित मार्ग हैं, और इन दो मार्गों में से कौन सा उपयोग करना है, यह चुनने की समस्या, इस तरह से कि सभी तारों को परिपथ की परत में रूट किया जा सकता है, को 2-संतुष्टि उदाहरण के रूप में हल किया जा सकता है।<ref>{{citation|first1=Raghunath|last1=Raghavan|first2= James|last2=Cohoon|first3=Sartaj|last3=Sahni|author3-link=Sartaj Sahni|title=Single bend wiring|journal=Journal of Algorithms|volume=7|issue=2|year=1986|pages=232–237|doi=10.1016/0196-6774(86)90006-4}}.</ref> | ||
{{harvtxt|बोरोस|हैमर |मिनौक्स|रडर |1999}} अन्य वीएलएसआई डिज़ाइन समस्या पर विचार करें: परिपथ डिज़ाइन में प्रत्येक मॉड्यूल को मिरर-रिवर्स करना है या नहीं, इसका प्रश्न। यह मिरर रिवर्सल मॉड्यूल के संचालन को अपरिवर्तित छोड़ देता है, किन्तु यह उन बिंदुओं के क्रम को बदल देता है जिन पर मॉड्यूल के इनपुट और आउटपुट सिग्नल इससे जुड़ते हैं, संभवतः यह बदल जाता है कि मॉड्यूल बाकी डिज़ाइन में कितनी अच्छी तरह फिट बैठता है। बोरोस एट अल. समस्या के सरलीकृत संस्करण पर विचार करें जिसमें मॉड्यूल पहले से ही ही रैखिक चैनल के साथ रखे गए हैं, जिसमें मॉड्यूल के बीच तारों को रूट किया जाना चाहिए, और चैनल के घनत्व पर निश्चित सीमा होती है (सिग्नलों की अधिकतम संख्या जो चैनल के किसी भी क्रॉस-सेक्शन से गुज़रनी चाहिए)। उनका मानना है कि समस्या के इस संस्करण को 2-संतुष्टि उदाहरण के रूप में हल किया जा सकता है, जिसमें बाधाएं मॉड्यूल के जोड़े के उन्मुखीकरण से संबंधित हैं जो सीधे दूसरे से चैनल के पार हैं। परिणामस्वरूप, बाइनरी खोज करके | {{harvtxt|बोरोस|हैमर |मिनौक्स|रडर |1999}} अन्य वीएलएसआई डिज़ाइन समस्या पर विचार करें: परिपथ डिज़ाइन में प्रत्येक मॉड्यूल को मिरर-रिवर्स करना है या नहीं, इसका प्रश्न। यह मिरर रिवर्सल मॉड्यूल के संचालन को अपरिवर्तित छोड़ देता है, किन्तु यह उन बिंदुओं के क्रम को बदल देता है जिन पर मॉड्यूल के इनपुट और आउटपुट सिग्नल इससे जुड़ते हैं, संभवतः यह बदल जाता है कि मॉड्यूल बाकी डिज़ाइन में कितनी अच्छी तरह फिट बैठता है। बोरोस एट अल. समस्या के सरलीकृत संस्करण पर विचार करें जिसमें मॉड्यूल पहले से ही ही रैखिक चैनल के साथ रखे गए हैं, जिसमें मॉड्यूल के बीच तारों को रूट किया जाना चाहिए, और चैनल के घनत्व पर निश्चित सीमा होती है (सिग्नलों की अधिकतम संख्या जो चैनल के किसी भी क्रॉस-सेक्शन से गुज़रनी चाहिए)। उनका मानना है कि समस्या के इस संस्करण को 2-संतुष्टि उदाहरण के रूप में हल किया जा सकता है, जिसमें बाधाएं मॉड्यूल के जोड़े के उन्मुखीकरण से संबंधित हैं जो सीधे दूसरे से चैनल के पार हैं। परिणामस्वरूप, बाइनरी खोज करके अधिकतम घनत्व की गणना भी कुशलतापूर्वक की जा सकती है, जिसमें प्रत्येक चरण में 2-संतुष्टि उदाहरण का समाधान सम्मिलित होता है।<ref>{{citation|first1=Endre|last1=Boros|first2=Peter Ladislaw|last2=Hammer|author2-link=Peter Ladislaw Hammer|first3=Michel|last3=Minoux|first4=David J., Jr.|last4=Rader|title=Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization|journal=[[Discrete Applied Mathematics]]|volume=90|issue=1–3|year=1999|pages=69–88|doi=10.1016/S0166-218X(98)00114-0}}.</ref> | ||
===[[डेटा क्लस्टरिंग]]=== | ===[[डेटा क्लस्टरिंग]]=== | ||
इस प्रकार के [[मीट्रिक स्थान]] में डेटा को दो समूहों में क्लस्टर करने का विधि क्लस्टर को इस तरह से चुनना है जिससे क्लस्टर के [[व्यास]] के योग को कम किया जा सके, जहां किसी एकल क्लस्टर का व्यास उसके किन्हीं दो बिंदुओं के बीच की सबसे बड़ी दूरी है। यह अधिकतम क्लस्टर आकार को कम करने के लिए बेहतर है, जिससे विभिन्न समूहों को बहुत समान अंक आवंटित किए जा सकते हैं। यदि दो समूहों के लक्ष्य व्यास ज्ञात हैं, तो 2-संतुष्टि उदाहरण को हल करके उन लक्ष्यों को प्राप्त करने वाली क्लस्टरिंग पाई जा सकती है। उदाहरण में प्रति बिंदु वेरिएबल है, जो दर्शाता है कि वह बिंदु पहले क्लस्टर से संबंधित है या दूसरे क्लस्टर से। जब भी कोई दो बिंदु दूसरे से इतने दूर होते हैं कि दोनों ही क्लस्टर से संबंधित नहीं होते हैं, तो उदाहरण में खंड जोड़ा जाता है जो इस असाइनमेंट को रोकता है। | |||
जब व्यक्तिगत क्लस्टर व्यास अज्ञात हों तो उसी विधि का उपयोग सबरूटीन के रूप में भी किया जा सकता है। यह जांचने के लिए कि क्या व्यास का दिया गया योग अलग-अलग क्लस्टर व्यास को जाने बिना प्राप्त किया जा सकता है, कोई लक्ष्य व्यास के सभी अधिकतम जोड़े का प्रयास कर सकता है जो अधिकतम दिए गए योग को जोड़ता है, व्यास की प्रत्येक जोड़ी को 2-संतुष्टिशीलता उदाहरण के रूप में दर्शाता है और यह निर्धारित करने के लिए 2-संतोषजनक एल्गोरिदम का उपयोग करता है कि क्या उस जोड़ी को क्लस्टरिंग द्वारा महसूस किया जा सकता है। व्यासों का | जब व्यक्तिगत क्लस्टर व्यास अज्ञात हों तो उसी विधि का उपयोग सबरूटीन के रूप में भी किया जा सकता है। यह जांचने के लिए कि क्या व्यास का दिया गया योग अलग-अलग क्लस्टर व्यास को जाने बिना प्राप्त किया जा सकता है, कोई लक्ष्य व्यास के सभी अधिकतम जोड़े का प्रयास कर सकता है जो अधिकतम दिए गए योग को जोड़ता है, व्यास की प्रत्येक जोड़ी को 2-संतुष्टिशीलता उदाहरण के रूप में दर्शाता है और यह निर्धारित करने के लिए 2-संतोषजनक एल्गोरिदम का उपयोग करता है कि क्या उस जोड़ी को क्लस्टरिंग द्वारा महसूस किया जा सकता है। व्यासों का अधिकतम योग ज्ञात करने के लिए कोई बाइनरी खोज कर सकता है जिसमें प्रत्येक चरण इस प्रकार का व्यवहार्यता परीक्षण होता है। यही दृष्टिकोण क्लस्टरिंग को खोजने के लिए भी कार्य करता है जो क्लस्टर व्यास के योग के अतिरिक्त अन्य संयोजनों को अनुकूलित करता है, और जो क्लस्टर के आकार को मापने के लिए मनमाने ढंग से असमानता संख्याओं (मीट्रिक स्थान में दूरी के अतिरिक्त ) का उपयोग करता है।<ref>{{citation|first1=P.|last1=Hansen|first2=B.|last2=Jaumard|author2-link= Brigitte Jaumard |title=Minimum sum of diameters clustering|journal=Journal of Classification|volume=4|issue=2|year=1987|pages=215–226|doi=10.1007/BF01896987|s2cid=120583429}}.</ref> इस एल्गोरिथम के लिए समय सीमा 2-संतोषजनक उदाहरणों के अनुक्रम को हल करने के समय पर हावी है जो एक-दूसरे से निकटता से संबंधित हैं, और {{harvtxt|रामनाथ|2004}} दिखाता है कि इन संबंधित उदाहरणों को एक-दूसरे से स्वतंत्र रूप से हल करने की तुलना में अधिक तेज़ी से कैसे हल किया जाए, तथा {{math|''O''(''n''<sup>3</sup>)}} व्यास के योग की क्लस्टरिंग समस्या के लिए जिससे कुल समय सीमा तय हो सके ।<ref>{{citation|first1=Sarnath|last1=Ramnath|title=Dynamic digraph connectivity hastens minimum sum-of-diameters clustering|journal=[[SIAM Journal on Discrete Mathematics]]|volume=18|issue=2|pages=272–286|year=2004|doi=10.1137/S0895480102396099}}.</ref> | ||
===शेड्यूलिंग=== | ===शेड्यूलिंग=== | ||
{{harvtxt|इवेन |इटाई|शमीर|1976}} कक्षा समय-निर्धारण के मॉडल पर विचार करें जिसमें छात्रों के प्रत्येक समूह को पढ़ाने के लिए n शिक्षकों का समूह निर्धारित किया जाना चाहिए। उस शिक्षक के प्रति सप्ताह घंटों की संख्या <math>i</math> समूह के साथ बिताता है <math>j</math> प्रविष्टि द्वारा वर्णित है <math>R_{ij}</math> | |||