सशर्त संभावनाओं की विधि: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
गणित और [[कंप्यूटर विज्ञान|'''कंप्यूटर विज्ञान''']] में, वांछित संयोजक गुणों के साथ गणितीय वस्तुओं के अस्तित्व को प्रमाणित करने के लिए '''प्रोबबिलिस्टिक मेथड''' | गणित और [[कंप्यूटर विज्ञान|'''कंप्यूटर विज्ञान''']] में, वांछित संयोजक गुणों के साथ गणितीय वस्तुओं के अस्तित्व को प्रमाणित करने के लिए '''प्रोबबिलिस्टिक मेथड''' का उपयोग किया जाता है। अतः यह प्रमाण प्रोबबिलिस्टिक हैं - वे यह दिखाकर कार्य करते हैं कि कुछ प्रोबबिलिस्टिक डिस्ट्रीब्यूशन से चुनी गई रेनडोमाइसड वस्तु में पोसिटिव संभावना के साथ वांछित गुण होते हैं। फलस्वरूप, वे नॉन-कॉनस्ट्रूकटिव प्रमाण हैं - वे वांछित वस्तुओं की गणना के लिए कुशल विधि का स्पष्ट रूप से वर्णन नहीं करते हैं। | ||
मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक {{harv|Spencer|1987}}, और {{harv|राघवन|1988}} इस प्रकार के प्रमाण का, अधिक स्पष्ट अर्थ है, कुशल डेटरमिनिस्टिक एल्गोरिदम में परिवर्तित करता है, जो वांछित गुणों के साथ किसी वस्तु की गणना करने का | मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक {{harv|Spencer|1987}}, और {{harv|राघवन|1988}} इस प्रकार के प्रमाण का, अधिक स्पष्ट अर्थ है, कुशल डेटरमिनिस्टिक एल्गोरिदम में परिवर्तित करता है, जो वांछित गुणों के साथ किसी वस्तु की गणना करने का प्रमाण देता है। अर्थात विधि रेनडोमाइसड प्रमाण. मूल विचार रेनडोमाइसड प्रयोग में प्रत्येक रैंडम चॉइस को डेटरमिनिस्टिक चॉइस से प्रतिस्थापित करना है, जिससे अब तक के विकल्पों को देखते हुए विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखा जा सकता है। | ||
यह विधि रेनडोमाइसड | यह विधि रेनडोमाइसड राउंडिंग के संदर्भ में विशेष रूप से प्रासंगिक है (जो अप्प्रोक्सीमेसन एल्गोरिदम को डिजाइन करने के लिए प्रोबबिलिस्टिक विधि का उपयोग करती है)। | ||
कंडीशनल प्रोबबिलिस्टिक की पद्धति को प्रयुक्त | कंडीशनल प्रोबबिलिस्टिक की पद्धति को प्रयुक्त करते समय, तकनीकी शब्द पेस्सिमिस्टिक एस्टीमेटर प्रमाण के अंतर्निहित वास्तविक कंडीशनल प्रोबबिलिस्टिक (या कंडीशनल अपेक्षा) के स्थान पर उपयोग की जाने वाली मात्रा को संदर्भित करता है। | ||
== अवलोकन == | == अवलोकन == | ||
{{harv|राघवन|1988}} यह विवरण देता है: | {{harv|राघवन|1988}} यह विवरण देता है: | ||
: इस प्रकार से हम प्रोबबिलिस्टिक | : इस प्रकार से हम प्रोबबिलिस्टिक विधि का उपयोग करके सिद्ध रूप से सही अनुमानित समाधान के अस्तित्व को दिखाते हैं... [फिर हम] दिखाते हैं कि प्रोबबिलिस्टिक अस्तित्व प्रमाण का अधिक स्पष्ट अर्थ है, कि डेटरमिनिस्टिक को अप्प्रोक्सीमेसन एल्गोरिदम में परिवर्तित किया जा सकता है। | ||
(राघवन रेनडोमाइसड | (राघवन रेनडोमाइसड पूर्णांकन के संदर्भ में विधि पर चर्चा कर रहे हैं, किन्तु यह सामान्य रूप से प्रोबबिलिस्टिक विधि के साथ कार्य करता है।) | ||
[[File:Method of conditional probabilities.png|thumb|450px|right|मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक]]इस प्रकार से विधि को प्रोबबिलिस्टिक | [[File:Method of conditional probabilities.png|thumb|450px|right|मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक]]इस प्रकार से विधि को प्रोबबिलिस्टिक प्रमाण पर प्रयुक्त करने के लिए, प्रमाण में रेनडोमाइसड रूप से चुनी गई है और वस्तु को रेनडोमाइसड प्रयोग द्वारा चुना जाना चाहिए जिसमें छोटे रैंडम चॉइस का अनुक्रम सम्मिलित होती है। | ||
अतः सिद्धांत को स्पष्ट करने के लिए यहां छोटा सा उदाहरण दिया गया है। | अतः सिद्धांत को स्पष्ट करने के लिए यहां छोटा सा उदाहरण दिया गया है। | ||
: लेम्मा: ''तीन सिक्कों को उछालना संभव है जिससे | : लेम्मा: ''तीन सिक्कों को उछालना संभव है जिससे टेल्स की संख्या कम से कम 2 हो।'' | ||
: ''प्रोबबिलिस्टिक | : ''प्रोबबिलिस्टिक प्रमाण'' यदि तीन सिक्कों को रेनडोमाइसड रूप से उछाला जाता है, तो टेल्स की अपेक्षित संख्या 1.5 है। इस प्रकार, कुछ परिणाम (सिक्के उछालने का विधि ) होना चाहिए जिससे टेल्स की संख्या कम से कम 1.5 हो। चूँकि टेल्स की संख्या पूर्णांक है, ऐसे परिणाम में कम से कम 2 टेल्स होती हैं। ''प्रश्न'' | ||
इस उदाहरण में रेनडोमाइसड | इस उदाहरण में रेनडोमाइसड प्रयोग में तीन निष्पक्ष सिक्कों को उछालना सम्मिलित किया है। और प्रयोग को आसन्न चित्र में रूट वाले ट्री द्वारा दर्शाया गया है। अतः यह आठ परिणाम हैं, प्रत्येक ट्री में लीफ के अनुरूप है। रेनडोमाइसड प्रयोग का परीक्षण रूट (ट्री में शीर्ष नोड, जहां कोई सिक्का नहीं उछाला गया है) से लीफ तक रेनडोमाइसड चलने से मेल खाता है। सफल परिणाम वे हैं जिनमें कम से कम दो सिक्के पीछे आए। किन्तु ट्री में आंतरिक नोड्स आंशिक रूप से निर्धारित परिणामों के अनुरूप हैं, जहां अब तक केवल 0, 1, या 2 सिक्के ही उछाले गए हैं। | ||
कंडीशनल प्रोबबिलिस्टिक की पद्धति को प्रयुक्त | कंडीशनल प्रोबबिलिस्टिक की पद्धति को प्रयुक्त करने के लिए, जैसे-जैसे प्रयोग चरण दर चरण आगे बढ़ता है, ''अब तक के विकल्पों को देखते हुए विफलता की कंडीशनल प्रोबबिलिस्टिक'' पर ध्यान केंद्रित किया जाता है। | ||
चूंकि आरेख में, प्रत्येक नोड को इस कंडीशनल प्रोबबिलिस्टिक के साथ लेबल किया गया है। (उदाहरण के लिए, यदि केवल प्रथम सिक्का उछाला गया है, और वह पट आता है, तो यह मूल के द्वतीय चाइल्ड से मेल खाता है। अतः उस आंशिक स्थिति पर आधारित, विफलता की संभावना 0.25 है।) | चूंकि आरेख में, प्रत्येक नोड को इस कंडीशनल प्रोबबिलिस्टिक के साथ लेबल किया गया है। (उदाहरण के लिए, यदि केवल प्रथम सिक्का उछाला गया है, और वह पट आता है, तो यह मूल के द्वतीय चाइल्ड से मेल खाता है। अतः उस आंशिक स्थिति पर आधारित, विफलता की संभावना 0.25 है।) | ||
मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक रेनडोमाइसड | मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक रेनडोमाइसड प्रयोग में रेनडोमाइसड रूट-टू-लीफ वॉक को डेटरमिनिस्टिक रूट-टू-लीफ वॉक द्वारा प्रतिस्थापित करती है, जहां प्रत्येक चरण को निम्नलिखित अपरिवर्तनीय बनाए रखने के लिए चुना जाता है: | ||
:: ''वर्तमान स्थिति को देखते हुए विफलता की कंडीशनल प्रोबबिलिस्टिक 1 से कम है।'' | :: ''वर्तमान स्थिति को देखते हुए विफलता की कंडीशनल प्रोबबिलिस्टिक 1 से कम है।'' | ||
इस प्रकार, लेबल 0 वाले लीफ पर पहुंचने की प्रमाण | इस प्रकार, लेबल 0 वाले लीफ पर पहुंचने की प्रमाण है, अर्थात सफल परिणाम है। | ||
किन्तु अपरिवर्तनीय प्रारंभ में (मूल पर) पर्याप्त रहता है, क्योंकि मूल प्रमाण से पता चला है कि विफलता की (बिना नियम ) संभावना 1 से कम है। किसी भी आंतरिक नोड पर कंडीशनल प्रोबबिलिस्टिक उसके चाइल्ड | किन्तु अपरिवर्तनीय प्रारंभ में (मूल पर) पर्याप्त रहता है, क्योंकि मूल प्रमाण से पता चला है कि विफलता की (बिना नियम ) संभावना 1 से कम है। किसी भी आंतरिक नोड पर कंडीशनल प्रोबबिलिस्टिक उसके चाइल्ड की कंडीशनल प्रोबबिलिस्टिक का औसत है। पश्चात वाली संपत्ति महत्वपूर्ण है क्योंकि इसका तात्पर्य है कि ''किसी भी आंतरिक नोड जिसकी कंडीशनल प्रोबबिलिस्टिक 1 से कम है, में कम से कम चाइल्ड है जिसकी कंडीशनल प्रोबबिलिस्टिक 1 से कम है।'' इस प्रकार, किसी भी आंतरिक नोड से, कोई हमेशा कुछ चाइल्ड को चुन सकता है जिससे अपरिवर्तनीय को बनाए रखा जा सके। चूँकि अंत में अपरिवर्तनीयता कायम रहती है, जब चलना लीफ पर पहुँचता है और सभी विकल्प निर्धारित हो चुके होते हैं, तो इस तरह से पहुँचा गया परिणाम सफल होना चाहिए। | ||
== दक्षता == | == दक्षता == | ||
विधि के विशिष्ट अनुप्रयोग में, लक्ष्य उचित रूप से कुशल एल्गोरिदम द्वारा परिणामी डेटरमिनिस्टिक प्रक्रिया को कार्यान्वित करने में सक्षम होना है (कुशल शब्द का सामान्यतः | विधि के विशिष्ट अनुप्रयोग में, लक्ष्य उचित रूप से कुशल एल्गोरिदम द्वारा परिणामी डेटरमिनिस्टिक प्रक्रिया को कार्यान्वित करने में सक्षम होना है (कुशल शब्द का सामान्यतः एल्गोरिदम होता है जो बहुपद समय में चलता है), तथापि सामान्यतः संभावित परिणामों की संख्या अधिक उच्च हो (घातीय रूप से बड़ा)। उदाहरण के लिए, सिक्का उछालने के कार्य पर विचार करें, किन्तु उच्च n के लिए इसे n फ्लिप तक विस्तारित किया गया है। | ||
आदर्श स्थिति में, आंशिक स्थिति (ट्री | आदर्श स्थिति में, आंशिक स्थिति (ट्री में नोड) को देखते हुए, विफलता की कंडीशनल प्रोबबिलिस्टिक (नोड पर लेबल) की गणना कुशलतापूर्वक और स्पष्ट रूप से की जा सकती है। (उपर्युक्त उदाहरण इस प्रकार है।) यदि ऐसा है, तो एल्गोरिदम वर्तमान नोड के प्रत्येक चाइल्ड पर कंडीशनल प्रोबबिलिस्टिक की गणना करके अगले नोड का चयन कर सकता है, फिर किसी भी चाइल्ड पर जा सकता है जिसकी कंडीशनल प्रोबबिलिस्टिक कम 1 से अधिक है जैसा कि ऊपर चर्चा की गई है, ऐसे नोड होने की प्रमाण है। | ||
दुर्भाग्य से, अधिकांश अनुप्रयोगों में, विफलता की कंडीशनल प्रोबबिलिस्टिक की कुशलता से गणना करना सरल | दुर्भाग्य से, अधिकांश अनुप्रयोगों में, विफलता की कंडीशनल प्रोबबिलिस्टिक की कुशलता से गणना करना सरल नहीं है। इससे निपटने के लिए दो मानक और संबंधित तकनीकें हैं: | ||
* 'कंडीशनल अपेक्षा का उपयोग करना:' अनेक प्रोबबिलिस्टिक प्रमाण इस प्रकार कार्य | * 'कंडीशनल अपेक्षा का उपयोग करना:' अनेक प्रोबबिलिस्टिक प्रमाण इस प्रकार कार्य करते हैं: वे स्पष्ट रूप से रेनडोमाइसड वेरिएबल Q को परिभाषित करते हैं, दिखाते हैं कि (i) Q की अपेक्षा अधिकतम (या कम से कम) कुछ सीमा मूल्य है, और (ii) किसी भी परिणाम जहां Q अधिकतम (कम से कम) इस सीमा पर है, परिणाम सफल है। तब (i) का अर्थ है कि परिणाम उपस्तिथ है जहां Q अधिकतम (कम से कम) सीमा है, और इसका और (ii) का अर्थ है कि सफल परिणाम है। (उपरोक्त उदाहरण में, Q टेल्स की संख्या है, जो कम से कम सीमा 1.5 होनी चाहिए। अनेक अनुप्रयोगों में, Q किसी दिए गए परिणाम में होने वाली बैड इवेंट्स (आवश्यक नहीं कि असंबद्ध) की संख्या है, जहां प्रत्येक बैड इवेंट्स मेल खाती है तरह से प्रयोग विफल हो सकता है, और घटित होने वाली बैड इवेंट्स की अपेक्षित संख्या 1 से कम है।) | ||
इस स्तिथि | इस स्तिथि में, विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखने के लिए, Q की कंडीशनल अपेक्षा को सीमा से नीचे (या ऊपर) रखना पर्याप्त है। ऐसा करने के लिए, विफलता की कंडीशनल प्रोबबिलिस्टिक की गणना करने के अतिरिक्त , एल्गोरिदम Q की कंडीशनल अपेक्षा की गणना करता है और तदनुसार आगे बढ़ता है: प्रत्येक आंतरिक नोड पर, कुछ चाइल्ड होते हैं जिनकी कंडीशनल अपेक्षा अधिकतम (कम से कम) नोड की कंडीशनल अपेक्षा होती है; एल्गोरिथ्म वर्तमान नोड से ऐसे चाइल्ड की ओर बढ़ता है, इस प्रकार कंडीशनल अपेक्षा को सीमा से नीचे (ऊपर) रखता है। | ||
* पेस्सिमिस्टिक एस्टीमेटर | * पेस्सिमिस्टिक एस्टीमेटर का उपयोग करना:' कुछ स्तिथि में, मात्रा Q की स्पष्ट कंडीशनल अपेक्षा के लिए प्रॉक्सी के रूप में, उचित रूप से टाइट सीमा का उपयोग किया जाता है जिसे पेस्सिमिस्टिक एस्टीमेटर कहा जाता है। पेस्सिमिस्टिक एस्टीमेटर वर्तमान स्थिति का कार्य है। वर्तमान स्थिति को देखते हुए यह Q की कंडीशनल अपेक्षा के लिए ऊपरी (या निचला) होना चाहिए, और यह प्रयोग के प्रत्येक रेनडोमाइसड चरण के साथ अपेक्षा में गैर-बढ़ती (या गैर-घटती) होनी चाहिए। सामान्यतः, अच्छे पेस्सिमिस्टिक एस्टीमेटर की गणना मूल प्रमाण के तर्क को स्पष्ट रूप से विखंडित करके की जा सकती है। | ||
== कंडीशनल अपेक्षाओं का उपयोग करने वाला उदाहरण == | == कंडीशनल अपेक्षाओं का उपयोग करने वाला उदाहरण == | ||
| Line 55: | Line 55: | ||
=== मैक्स-कट लेम्मा === | === मैक्स-कट लेम्मा === | ||
किसी भी अप्रत्यक्ष ग्राफ़ (असतत गणित) | किसी भी अप्रत्यक्ष ग्राफ़ (असतत गणित) G = (V, E) को देखते हुए, [[अधिकतम कटौती|अधिकतम कट]] समस्या ग्राफ़ के प्रत्येक शीर्ष को दो रंगों (जैसे काले या सफेद) में से के साथ रंगना है जिससे किनारों की संख्या को अधिकतम किया जा सके जिनके अंतिम बिंदु हैं अलग - अलग रंग। (कहो ऐसी धार कटी है।) | ||
'मैक्स-कट लेम्मा:' किसी भी ग्राफ G = (V, E) में, कम से कम |E|/2 किनारों को काटा जा सकता है। | 'मैक्स-कट लेम्मा:' किसी भी ग्राफ G = (V, E) में, कम से कम |E|/2 किनारों को काटा जा सकता है। | ||
'प्रोबबिलिस्टिक | 'प्रोबबिलिस्टिक प्रमाण।' सफेद सिक्का उछालकर प्रत्येक शीर्ष को काला या सफेद रंग दें। गणना के अनुसार, ''E'' में किसी भी किनारे ''E'' के लिए, इसके कटने की संभावना 1/2 है। इस प्रकार, अपेक्षित मान या रैखिकता के अनुसार, काटे गए किनारों की अपेक्षित संख्या |E|/2 है। इस प्रकार, ऐसा रंग उपस्तिथ है जो कम से कम |E|/2 किनारों को क्यूईडी काटता है। | ||
=== कंडीशनल अपेक्षाओं के साथ मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक === | === कंडीशनल अपेक्षाओं के साथ मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक === | ||
मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक को प्रयुक्त | मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक को प्रयुक्त करने के लिए, पहले रेनडोमाइसड प्रयोग को छोटे रेनडोमाइसड चरणों के अनुक्रम के रूप में मॉडल किया जाता है। इस स्तिथि में प्रत्येक चरण को किसी विशेष शीर्ष के लिए रंग की चॉइस के रूप में मानना स्वाभाविक है (इसलिए |V| चरण हैं)। | ||
इसके पश्चात , प्रत्येक चरण में रैंडम चॉइस | इसके पश्चात , प्रत्येक चरण में रैंडम चॉइस को डेटरमिनिस्टिक चॉइस से परिवर्तन , जिससे विफलता की कंडीशनल प्रोबबिलिस्टिक को बनाए रखा जा सके, अब तक रंगे गए शीर्षों को 1 से नीचे दिया गया है। (यहां विफलता का अर्थ है कि अंततः |E|/2 से कम किनारे काटे गए हैं।) | ||
इस स्तिथि | इस स्तिथि में, विफलता की कंडीशनल प्रोबबिलिस्टिक की गणना करना सरल नहीं है। वास्तव में, मूल प्रमाण सीधे विफलता की संभावना की गणना नहीं करता था; इसके अतिरिक्त, प्रमाण ने यह दिखाकर कार्य किया कि कटे हुए किनारों की अपेक्षित संख्या कम से कम |ई|/2 थी। | ||
माना रेनडोमाइसड | माना रेनडोमाइसड वेरिएबल Q कटे हुए किनारों की संख्या है। विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखने के लिए, Q की कंडीशनल अपेक्षा को सीमा |E|/2 पर या उससे ऊपर रखना पर्याप्त है। (ऐसा इसलिए है क्योंकि जब तक Q की कंडीशनल अपेक्षा कम से कम |E|/2 है, तब तक कुछ अभी भी पहुंच योग्य परिणाम होना चाहिए जहां Q कम से कम |E|/2 है, इसलिए ऐसे परिणाम तक पहुंचने की कंडीशनल प्रोबबिलिस्टिक धनात्मक है।) Q की कंडीशनल अपेक्षा को |E|/2 या उससे ऊपर रखने के लिए, एल्गोरिदम, प्रत्येक चरण में, विचाराधीन शीर्ष को रंग देगा जिससे Q की परिणामी कंडीशनल अपेक्षा को अधिकतम किया जा सकता है। यह पर्याप्त है, क्योंकि कुछ चाइल्ड होंगे जिनकी कंडीशनल अपेक्षा कम से कम वर्तमान स्थिति है की कंडीशनल अपेक्षा (और इस प्रकार कम से कम |ई|/2)। | ||
यह देखते हुए कि कुछ शीर्ष पहले से ही रंगीन हैं, यह कंडीशनल अपेक्षा क्या है? मूल प्रमाण के तर्क के पश्चात, कटे हुए किनारों की संख्या की कंडीशनल अपेक्षा है | यह देखते हुए कि कुछ शीर्ष पहले से ही रंगीन हैं, यह कंडीशनल अपेक्षा क्या है? मूल प्रमाण के तर्क के पश्चात, कटे हुए किनारों की संख्या की कंडीशनल अपेक्षा है | ||
:: किनारों की संख्या जिनके अंतिम बिंदु अब तक भिन्न-भिन्न | :: किनारों की संख्या जिनके अंतिम बिंदु अब तक भिन्न-भिन्न रंग के हैं | ||
:: + (1/2)*(कम से कम समापन बिंदु वाले किनारों की संख्या जो अभी तक रंगीन नहीं हुई है)। | :: + (1/2)*(कम से कम समापन बिंदु वाले किनारों की संख्या जो अभी तक रंगीन नहीं हुई है)। | ||
=== एल्गोरिथम === | === एल्गोरिथम === | ||
इस प्रकार से उपरोक्त कंडीशनल अपेक्षा के परिणामी मूल्य को अधिकतम करने के लिए एल्गोरिदम प्रत्येक शीर्ष को रंग देता है। यह कंडीशनल अपेक्षा को |ई|/2 या उससे ऊपर रखने की प्रमाण | इस प्रकार से उपरोक्त कंडीशनल अपेक्षा के परिणामी मूल्य को अधिकतम करने के लिए एल्गोरिदम प्रत्येक शीर्ष को रंग देता है। यह कंडीशनल अपेक्षा को |ई|/2 या उससे ऊपर रखने की प्रमाण है, और इसलिए विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखने की प्रमाण है, जो परिवर्तन में सफल परिणाम की प्रमाण देता है। और गणना द्वारा, एल्गोरिथ्म निम्नलिखित को सरल बनाता है: | ||
1. V में प्रत्येक शीर्ष ''u'' के लिए (किसी भी क्रम में): | 1. V में प्रत्येक शीर्ष ''u'' के लिए (किसी भी क्रम में): | ||
| Line 85: | Line 85: | ||
4. नहीं तो तुम्हें काला रंग प्राप्त होगा. | 4. नहीं तो तुम्हें काला रंग प्राप्त होगा. | ||
इसकी व्युत्पत्ति के कारण, यह डेटरमिनिस्टिक एल्गोरिदम दिए गए ग्राफ़ के कम से कम आधे किनारों को काटने की प्रमाण | इसकी व्युत्पत्ति के कारण, यह डेटरमिनिस्टिक एल्गोरिदम दिए गए ग्राफ़ के कम से कम आधे किनारों को काटने की प्रमाण देता है। (यह इसे मैक्स-कट के लिए अधिकतम कट या अप्प्रोक्सीमेसन एल्गोरिदम 0.5-अप्प्रोक्सीमेसन एल्गोरिदम बनाता है।) | ||
== पेस्सिमिस्टिक एस्टीमेटरों का उपयोग करने वाला उदाहरण == | == पेस्सिमिस्टिक एस्टीमेटरों का उपयोग करने वाला उदाहरण == | ||
| Line 93: | Line 93: | ||
=== तुरान का प्रमेय === | === तुरान का प्रमेय === | ||
तुरान के प्रमेय को बताने का विधि | तुरान के प्रमेय को बताने का विधि निम्नलिखित है: | ||
: किसी भी ग्राफ G = (V, E) में कम से कम |V|/(D+1) आकार का स्वतंत्र समुच्चय (ग्राफ सिद्धांत) होता है, जहां D = 2|E|/|V| ग्राफ़ की औसत डिग्री है. | : किसी भी ग्राफ G = (V, E) में कम से कम |V|/(D+1) आकार का स्वतंत्र समुच्चय (ग्राफ सिद्धांत) होता है, जहां D = 2|E|/|V| ग्राफ़ की औसत डिग्री है. | ||
=== तुरान के प्रमेय का प्रोबबिलिस्टिक | === तुरान के प्रमेय का प्रोबबिलिस्टिक प्रमाण === | ||
एक स्वतंत्र समुच्चय S के निर्माण के लिए निम्नलिखित रेनडोमाइसड | एक स्वतंत्र समुच्चय S के निर्माण के लिए निम्नलिखित रेनडोमाइसड प्रक्रिया पर विचार करें: | ||
1. रिक्त | 1. रिक्त समुच्चय होने के लिए S को आरंभ करें। | ||
2. V में प्रत्येक शीर्ष u के लिए रेनडोमाइसड | 2. V में प्रत्येक शीर्ष u के लिए रेनडोमाइसड क्रम में: | ||
3. यदि आपका कोई निकटतम | 3. यदि आपका कोई निकटतम S में नहीं है, तो S में u जोड़ें | ||
4. वापसी एस. | 4. वापसी एस. | ||
स्पष्ट रूप से प्रक्रिया स्वतंत्र समुच्चय की गणना करती है। कोई भी शीर्ष u जिसे उसके सभी निकटतम से पहले माना जाता है, उसे S में जोड़ा जाएगा। इस प्रकार, d(u) को u की डिग्री को निरूपित करने पर, संभावना है कि u को S में जोड़ा जाता है, कम से कम 1/(d(u)+1) है ). अपेक्षित मान या रैखिकता के अनुसार, S का अपेक्षित आकार कम से कम है | स्पष्ट रूप से प्रक्रिया स्वतंत्र समुच्चय की गणना करती है। कोई भी शीर्ष u जिसे उसके सभी निकटतम से पहले माना जाता है, उसे S में जोड़ा जाएगा। इस प्रकार, d(u) को u की डिग्री को निरूपित करने पर, संभावना है कि u को S में जोड़ा जाता है, कम से कम 1/(d(u)+1) है ). अपेक्षित मान या रैखिकता के अनुसार, S का अपेक्षित आकार कम से कम है | ||
| Line 111: | Line 111: | ||
=== पेस्सिमिस्टिक एस्टीमेटरों का उपयोग करके मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक === | === पेस्सिमिस्टिक एस्टीमेटरों का उपयोग करके मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक === | ||
इस स्तिथि | इस स्तिथि में, रेनडोमाइसड प्रक्रिया में |V| है पद। प्रत्येक चरण कुछ ऐसे शीर्षों पर विचार करता है जिन्हें अभी तक नहीं माना गया है और यदि उसके किसी भी निकटतम को अभी तक नहीं जोड़ा गया है तो उसे एस में जोड़ दिया जाता है। मान लें कि रेनडोमाइसड वेरिएबल Q, S में जोड़े गए शीर्षों की संख्या है। प्रमाण से पता चलता है कि E[Q] ≥ |V|/(D+1)। | ||
हम प्रत्येक रेनडोमाइसड | हम प्रत्येक रेनडोमाइसड चरण को डेटरमिनिस्टिक चरण से प्रतिस्थापित करेंगे जो Q की कंडीशनल अपेक्षा को |V|/(D+1) पर या उससे ऊपर रखता है। यह सफल परिणाम सुनिश्चित करेगा, अर्थात, जिसमें स्वतंत्र समुच्चय S का आकार कम से कम |V|/(D+1) हो, जो तुरान के प्रमेय में सीमा को साकार करता है। | ||
यह देखते हुए कि प्रथम t पद | यह देखते हुए कि प्रथम t पद उठाया जा चुका है, मान लीजिए S<sup>(t)</sup>अब तक जोड़े गए शीर्षों को दर्शाता है। जब ''R''<sup>(''t'')</sup> उन शीर्षों को दर्शाता है जिन पर अभी तक विचार नहीं किया गया है, और जिनका S<sup>(t)</sup> में कोई निकटतम नहीं है. पहले t चरणों को देखते हुए, मूल प्रमाण में तर्क के पश्चात, R<sup>(t)</sup> में कोई भी शीर्ष w दिया गया है में S में जोड़े जाने की कंडीशनल प्रोबबिलिस्टिक कम से कम 1/(d(w)+1) है, इसलिए Q की कंडीशनल अपेक्षा कम से कम है | ||
: <math>|S^{(t)}| ~+~ \sum_{w\in R^{(t)}} \frac{1}{d(w)+1}. </math> | : <math>|S^{(t)}| ~+~ \sum_{w\in R^{(t)}} \frac{1}{d(w)+1}. </math> | ||
मान लीजिये Q<sup>(t)</sup> उपर्युक्त मात्रा को दर्शाता है, जिसे कंडीशनल अपेक्षा के लिए पेस्सिमिस्टिक एस्टीमेटर' कहा जाता है। | मान लीजिये Q<sup>(t)</sup> उपर्युक्त मात्रा को दर्शाता है, जिसे कंडीशनल अपेक्षा के लिए पेस्सिमिस्टिक एस्टीमेटर' कहा जाता है। | ||
प्रमाण से पता चला कि पेस्सिमिस्टिक एस्टीमेटर प्रारंभ | प्रमाण से पता चला कि पेस्सिमिस्टिक एस्टीमेटर प्रारंभ में कम से कम |V|/(D+1) है। (अर्थात्, ''Q''<sup>(0)</sup> ≥ |''V''|/(''D''+1).) एल्गोरिदम पेस्सिमिस्टिक एस्टीमेटर को घटने से रोकने के लिए प्रत्येक विकल्प चुनेगा, अर्थात, जिससे ''Q''<sup>(''t''+1)</sup> ≥ ''Q''<sup>(''t'')</sup> प्रत्येक t के लिए। चूँकि पेस्सिमिस्टिक एस्टीमेटर कंडीशनल अपेक्षा पर निचली सीमा रखता है, यह सुनिश्चित करेगा कि कंडीशनल अपेक्षा |V|/(D+1) से ऊपर रहे, जो परिवर्तन में यह सुनिश्चित करेगा कि विफलता की कंडीशनल प्रोबबिलिस्टिक 1 से नीचे रहे है। | ||
मान लीजिए कि आप अगले ((t+1)-st) चरण में एल्गोरिथम द्वारा माना गया शीर्ष है। | मान लीजिए कि आप अगले ((t+1)-st) चरण में एल्गोरिथम द्वारा माना गया शीर्ष है। | ||
यदि आपका पहले से ही S में कोई निकटतम | यदि आपका पहले से ही S में कोई निकटतम है, तो आपको S में नहीं जोड़ा जाता है और (Q<sup>(t)</sup> के निरीक्षण द्वारा)), पेस्सिमिस्टिक एस्टीमेटर अपरिवर्तित है। यदि S में u का कोई निकटतम नहीं है, तब S में u जोड़ा जाता है। | ||
गणना के अनुसार, यदि u को शेष शीर्षों से रेनडोमाइसड | गणना के अनुसार, यदि u को शेष शीर्षों से रेनडोमाइसड रूप से चुना जाता है, तो पेस्सिमिस्टिक एस्टीमेटर में अपेक्षित वृद्धि गैर-ऋणात्मक है। ['गणना के अनुसार।' ''R''<sup>(''t'')</sup> में शीर्ष चुनने पर नियम , पेस्सिमिस्टिक एस्टीमेटर में दिए गए पद 1/(d(w)+1) को योग से हटा दिए जाने की संभावना अधिकतम (''d''(''w'')+1)/|''R''<sup>(''t'')</sup>| है, इसलिए योग में प्रत्येक पद में अपेक्षित कमी अधिकतम 1/|''R''<sup>(''t'')</sup>| है. जहाँ ''R''<sup>(''t''))</sup> योग में नियम इस प्रकार, योग में अपेक्षित कमी अधिकतम 1 है। इस मध्य, S का आकार 1 बढ़ जाता है।] | ||
इस प्रकार, आपके पास कुछ विकल्प उपस्तिथ होने चाहिए जो पेस्सिमिस्टिक एस्टीमेटर को कम होने से रोकते हैं। | इस प्रकार, आपके पास कुछ विकल्प उपस्तिथ होने चाहिए जो पेस्सिमिस्टिक एस्टीमेटर को कम होने से रोकते हैं। | ||
| Line 136: | Line 136: | ||
नीचे, ''N''<sup>(''t'')</sup>(''u'') ''R''<sup>(''t'')</sup> में u के निकटतम को दर्शाता है (अर्थात, आपके ऐसे निकटतम जो न तो S में हैं और न ही S में उनका कोई निकटतम है)। | नीचे, ''N''<sup>(''t'')</sup>(''u'') ''R''<sup>(''t'')</sup> में u के निकटतम को दर्शाता है (अर्थात, आपके ऐसे निकटतम जो न तो S में हैं और न ही S में उनका कोई निकटतम है)। | ||
1. रिक्त समुच्चय होने के लिए S को आरंभ करें। | 1. रिक्त समुच्चय होने के लिए S को आरंभ करें। | ||
2. जबकि एस में कोई निकटतम | 2. जबकि एस में कोई निकटतम नहीं होने के कारण अभी तक नहीं माना जाने वाला शीर्ष u उपस्तिथ है: | ||
3. S में ऐसा शीर्ष u जोड़ें जहां u न्यूनतम हो <math>\sum_{w\in N^{(t)}(u)\cup\{u\}} \frac{1}{d(w)+1}</math>. | 3. S में ऐसा शीर्ष u जोड़ें जहां u न्यूनतम हो <math>\sum_{w\in N^{(t)}(u)\cup\{u\}} \frac{1}{d(w)+1}</math>. | ||
4. वापसी S. | 4. वापसी S. | ||
| Line 142: | Line 142: | ||
=== एल्गोरिदम जो पेस्सिमिस्टिक एस्टीमेटर को अधिकतम नहीं करते === | === एल्गोरिदम जो पेस्सिमिस्टिक एस्टीमेटर को अधिकतम नहीं करते === | ||
मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक के कार्य | मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक के कार्य करने के लिए, यह पर्याप्त है यदि एल्गोरिदम पेस्सिमिस्टिक एस्टीमेटर को घटने (या बढ़ने, जैसा उपयुक्त हो) से रखता है। एल्गोरिदम को पेस्सिमिस्टिक एस्टीमेटर को अधिकतम (या न्यूनतम) करना आवश्यक नहीं है। यह एल्गोरिदम प्राप्त करने में कुछ लचीलापन देता है। इसके अतिरिक्त दो एल्गोरिदम इसे दर्शाते हैं। | ||
1. रिक्त | 1. रिक्त समुच्चय होने के लिए S को आरंभ करें। | ||
2. जबकि ग्राफ़ में शीर्ष u उपस्तिथ | 2. जबकि ग्राफ़ में शीर्ष u उपस्तिथ है जिसका S में कोई निकटतम नहीं है: | ||
3. S में ऐसा शीर्ष u जोड़ें, जहां u, d(u) (u की प्रारंभिक डिग्री) को न्यूनतम करता है। | 3. S में ऐसा शीर्ष u जोड़ें, जहां u, d(u) (u की प्रारंभिक डिग्री) को न्यूनतम करता है। | ||
4. वापसी एस. | 4. वापसी एस. | ||
1. रिक्त | 1. रिक्त समुच्चय होने के लिए S को आरंभ करें। | ||
2. जबकि शेष ग्राफ रिक्त | 2. जबकि शेष ग्राफ रिक्त नहीं है: | ||
3. S में शीर्ष u जोड़ें, जहां शेष ग्राफ़ में u की न्यूनतम डिग्री है। | 3. S में शीर्ष u जोड़ें, जहां शेष ग्राफ़ में u की न्यूनतम डिग्री है। | ||
4. ग्राफ़ से आप और उसके सभी निकटतम को हटा दें। | 4. ग्राफ़ से आप और उसके सभी निकटतम को हटा दें। | ||
| Line 160: | Line 160: | ||
जहां ''N''<sup>(''t'')</sup>(''u'') शेष ग्राफ़ में u के निकटतम को दर्शाता है (अर्थात, ''R''<sup>(''t'')</sup> में)।. | जहां ''N''<sup>(''t'')</sup>(''u'') शेष ग्राफ़ में u के निकटतम को दर्शाता है (अर्थात, ''R''<sup>(''t'')</sup> में)।. | ||
प्रथम एल्गोरिदम के लिए, शुद्ध वृद्धि गैर-ऋणात्मक | प्रथम एल्गोरिदम के लिए, शुद्ध वृद्धि गैर-ऋणात्मक है क्योंकि, u की चॉइस से, | ||
: <math>\sum_{w\in N^{(t)}(u)\cup\{u\}} \frac{1}{d(w)+1} \le (d(u)+1) \frac{1}{d(u)+1} = 1 </math>, | : <math>\sum_{w\in N^{(t)}(u)\cup\{u\}} \frac{1}{d(w)+1} \le (d(u)+1) \frac{1}{d(u)+1} = 1 </math>, | ||
| Line 166: | Line 166: | ||
जहां ''d(u)'' मूल ग्राफ़ में u की डिग्री है। | जहां ''d(u)'' मूल ग्राफ़ में u की डिग्री है। | ||
दूसरे एल्गोरिदम के लिए, शुद्ध वृद्धि गैर-ऋणात्मक | दूसरे एल्गोरिदम के लिए, शुद्ध वृद्धि गैर-ऋणात्मक है क्योंकि, u की चॉइस से, | ||
: <math>\sum_{w\in N^{(t)}(u)\cup\{u\}} \frac{1}{d(w)+1} \le (d'(u)+1) \frac{1}{d'(u)+1} = 1 </math>, | : <math>\sum_{w\in N^{(t)}(u)\cup\{u\}} \frac{1}{d(w)+1} \le (d'(u)+1) \frac{1}{d'(u)+1} = 1 </math>, | ||
Revision as of 14:06, 3 August 2023
गणित और कंप्यूटर विज्ञान में, वांछित संयोजक गुणों के साथ गणितीय वस्तुओं के अस्तित्व को प्रमाणित करने के लिए प्रोबबिलिस्टिक मेथड का उपयोग किया जाता है। अतः यह प्रमाण प्रोबबिलिस्टिक हैं - वे यह दिखाकर कार्य करते हैं कि कुछ प्रोबबिलिस्टिक डिस्ट्रीब्यूशन से चुनी गई रेनडोमाइसड वस्तु में पोसिटिव संभावना के साथ वांछित गुण होते हैं। फलस्वरूप, वे नॉन-कॉनस्ट्रूकटिव प्रमाण हैं - वे वांछित वस्तुओं की गणना के लिए कुशल विधि का स्पष्ट रूप से वर्णन नहीं करते हैं।
मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक (Spencer 1987), और (राघवन 1988) इस प्रकार के प्रमाण का, अधिक स्पष्ट अर्थ है, कुशल डेटरमिनिस्टिक एल्गोरिदम में परिवर्तित करता है, जो वांछित गुणों के साथ किसी वस्तु की गणना करने का प्रमाण देता है। अर्थात विधि रेनडोमाइसड प्रमाण. मूल विचार रेनडोमाइसड प्रयोग में प्रत्येक रैंडम चॉइस को डेटरमिनिस्टिक चॉइस से प्रतिस्थापित करना है, जिससे अब तक के विकल्पों को देखते हुए विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखा जा सकता है।
यह विधि रेनडोमाइसड राउंडिंग के संदर्भ में विशेष रूप से प्रासंगिक है (जो अप्प्रोक्सीमेसन एल्गोरिदम को डिजाइन करने के लिए प्रोबबिलिस्टिक विधि का उपयोग करती है)।
कंडीशनल प्रोबबिलिस्टिक की पद्धति को प्रयुक्त करते समय, तकनीकी शब्द पेस्सिमिस्टिक एस्टीमेटर प्रमाण के अंतर्निहित वास्तविक कंडीशनल प्रोबबिलिस्टिक (या कंडीशनल अपेक्षा) के स्थान पर उपयोग की जाने वाली मात्रा को संदर्भित करता है।
अवलोकन
(राघवन 1988) यह विवरण देता है:
- इस प्रकार से हम प्रोबबिलिस्टिक विधि का उपयोग करके सिद्ध रूप से सही अनुमानित समाधान के अस्तित्व को दिखाते हैं... [फिर हम] दिखाते हैं कि प्रोबबिलिस्टिक अस्तित्व प्रमाण का अधिक स्पष्ट अर्थ है, कि डेटरमिनिस्टिक को अप्प्रोक्सीमेसन एल्गोरिदम में परिवर्तित किया जा सकता है।
(राघवन रेनडोमाइसड पूर्णांकन के संदर्भ में विधि पर चर्चा कर रहे हैं, किन्तु यह सामान्य रूप से प्रोबबिलिस्टिक विधि के साथ कार्य करता है।)
इस प्रकार से विधि को प्रोबबिलिस्टिक प्रमाण पर प्रयुक्त करने के लिए, प्रमाण में रेनडोमाइसड रूप से चुनी गई है और वस्तु को रेनडोमाइसड प्रयोग द्वारा चुना जाना चाहिए जिसमें छोटे रैंडम चॉइस का अनुक्रम सम्मिलित होती है।
अतः सिद्धांत को स्पष्ट करने के लिए यहां छोटा सा उदाहरण दिया गया है।
- लेम्मा: तीन सिक्कों को उछालना संभव है जिससे टेल्स की संख्या कम से कम 2 हो।
- प्रोबबिलिस्टिक प्रमाण यदि तीन सिक्कों को रेनडोमाइसड रूप से उछाला जाता है, तो टेल्स की अपेक्षित संख्या 1.5 है। इस प्रकार, कुछ परिणाम (सिक्के उछालने का विधि ) होना चाहिए जिससे टेल्स की संख्या कम से कम 1.5 हो। चूँकि टेल्स की संख्या पूर्णांक है, ऐसे परिणाम में कम से कम 2 टेल्स होती हैं। प्रश्न
इस उदाहरण में रेनडोमाइसड प्रयोग में तीन निष्पक्ष सिक्कों को उछालना सम्मिलित किया है। और प्रयोग को आसन्न चित्र में रूट वाले ट्री द्वारा दर्शाया गया है। अतः यह आठ परिणाम हैं, प्रत्येक ट्री में लीफ के अनुरूप है। रेनडोमाइसड प्रयोग का परीक्षण रूट (ट्री में शीर्ष नोड, जहां कोई सिक्का नहीं उछाला गया है) से लीफ तक रेनडोमाइसड चलने से मेल खाता है। सफल परिणाम वे हैं जिनमें कम से कम दो सिक्के पीछे आए। किन्तु ट्री में आंतरिक नोड्स आंशिक रूप से निर्धारित परिणामों के अनुरूप हैं, जहां अब तक केवल 0, 1, या 2 सिक्के ही उछाले गए हैं।
कंडीशनल प्रोबबिलिस्टिक की पद्धति को प्रयुक्त करने के लिए, जैसे-जैसे प्रयोग चरण दर चरण आगे बढ़ता है, अब तक के विकल्पों को देखते हुए विफलता की कंडीशनल प्रोबबिलिस्टिक पर ध्यान केंद्रित किया जाता है।
चूंकि आरेख में, प्रत्येक नोड को इस कंडीशनल प्रोबबिलिस्टिक के साथ लेबल किया गया है। (उदाहरण के लिए, यदि केवल प्रथम सिक्का उछाला गया है, और वह पट आता है, तो यह मूल के द्वतीय चाइल्ड से मेल खाता है। अतः उस आंशिक स्थिति पर आधारित, विफलता की संभावना 0.25 है।)
मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक रेनडोमाइसड प्रयोग में रेनडोमाइसड रूट-टू-लीफ वॉक को डेटरमिनिस्टिक रूट-टू-लीफ वॉक द्वारा प्रतिस्थापित करती है, जहां प्रत्येक चरण को निम्नलिखित अपरिवर्तनीय बनाए रखने के लिए चुना जाता है:
- वर्तमान स्थिति को देखते हुए विफलता की कंडीशनल प्रोबबिलिस्टिक 1 से कम है।
इस प्रकार, लेबल 0 वाले लीफ पर पहुंचने की प्रमाण है, अर्थात सफल परिणाम है।
किन्तु अपरिवर्तनीय प्रारंभ में (मूल पर) पर्याप्त रहता है, क्योंकि मूल प्रमाण से पता चला है कि विफलता की (बिना नियम ) संभावना 1 से कम है। किसी भी आंतरिक नोड पर कंडीशनल प्रोबबिलिस्टिक उसके चाइल्ड की कंडीशनल प्रोबबिलिस्टिक का औसत है। पश्चात वाली संपत्ति महत्वपूर्ण है क्योंकि इसका तात्पर्य है कि किसी भी आंतरिक नोड जिसकी कंडीशनल प्रोबबिलिस्टिक 1 से कम है, में कम से कम चाइल्ड है जिसकी कंडीशनल प्रोबबिलिस्टिक 1 से कम है। इस प्रकार, किसी भी आंतरिक नोड से, कोई हमेशा कुछ चाइल्ड को चुन सकता है जिससे अपरिवर्तनीय को बनाए रखा जा सके। चूँकि अंत में अपरिवर्तनीयता कायम रहती है, जब चलना लीफ पर पहुँचता है और सभी विकल्प निर्धारित हो चुके होते हैं, तो इस तरह से पहुँचा गया परिणाम सफल होना चाहिए।
दक्षता
विधि के विशिष्ट अनुप्रयोग में, लक्ष्य उचित रूप से कुशल एल्गोरिदम द्वारा परिणामी डेटरमिनिस्टिक प्रक्रिया को कार्यान्वित करने में सक्षम होना है (कुशल शब्द का सामान्यतः एल्गोरिदम होता है जो बहुपद समय में चलता है), तथापि सामान्यतः संभावित परिणामों की संख्या अधिक उच्च हो (घातीय रूप से बड़ा)। उदाहरण के लिए, सिक्का उछालने के कार्य पर विचार करें, किन्तु उच्च n के लिए इसे n फ्लिप तक विस्तारित किया गया है।
आदर्श स्थिति में, आंशिक स्थिति (ट्री में नोड) को देखते हुए, विफलता की कंडीशनल प्रोबबिलिस्टिक (नोड पर लेबल) की गणना कुशलतापूर्वक और स्पष्ट रूप से की जा सकती है। (उपर्युक्त उदाहरण इस प्रकार है।) यदि ऐसा है, तो एल्गोरिदम वर्तमान नोड के प्रत्येक चाइल्ड पर कंडीशनल प्रोबबिलिस्टिक की गणना करके अगले नोड का चयन कर सकता है, फिर किसी भी चाइल्ड पर जा सकता है जिसकी कंडीशनल प्रोबबिलिस्टिक कम 1 से अधिक है जैसा कि ऊपर चर्चा की गई है, ऐसे नोड होने की प्रमाण है।
दुर्भाग्य से, अधिकांश अनुप्रयोगों में, विफलता की कंडीशनल प्रोबबिलिस्टिक की कुशलता से गणना करना सरल नहीं है। इससे निपटने के लिए दो मानक और संबंधित तकनीकें हैं:
- 'कंडीशनल अपेक्षा का उपयोग करना:' अनेक प्रोबबिलिस्टिक प्रमाण इस प्रकार कार्य करते हैं: वे स्पष्ट रूप से रेनडोमाइसड वेरिएबल Q को परिभाषित करते हैं, दिखाते हैं कि (i) Q की अपेक्षा अधिकतम (या कम से कम) कुछ सीमा मूल्य है, और (ii) किसी भी परिणाम जहां Q अधिकतम (कम से कम) इस सीमा पर है, परिणाम सफल है। तब (i) का अर्थ है कि परिणाम उपस्तिथ है जहां Q अधिकतम (कम से कम) सीमा है, और इसका और (ii) का अर्थ है कि सफल परिणाम है। (उपरोक्त उदाहरण में, Q टेल्स की संख्या है, जो कम से कम सीमा 1.5 होनी चाहिए। अनेक अनुप्रयोगों में, Q किसी दिए गए परिणाम में होने वाली बैड इवेंट्स (आवश्यक नहीं कि असंबद्ध) की संख्या है, जहां प्रत्येक बैड इवेंट्स मेल खाती है तरह से प्रयोग विफल हो सकता है, और घटित होने वाली बैड इवेंट्स की अपेक्षित संख्या 1 से कम है।)
इस स्तिथि में, विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखने के लिए, Q की कंडीशनल अपेक्षा को सीमा से नीचे (या ऊपर) रखना पर्याप्त है। ऐसा करने के लिए, विफलता की कंडीशनल प्रोबबिलिस्टिक की गणना करने के अतिरिक्त , एल्गोरिदम Q की कंडीशनल अपेक्षा की गणना करता है और तदनुसार आगे बढ़ता है: प्रत्येक आंतरिक नोड पर, कुछ चाइल्ड होते हैं जिनकी कंडीशनल अपेक्षा अधिकतम (कम से कम) नोड की कंडीशनल अपेक्षा होती है; एल्गोरिथ्म वर्तमान नोड से ऐसे चाइल्ड की ओर बढ़ता है, इस प्रकार कंडीशनल अपेक्षा को सीमा से नीचे (ऊपर) रखता है।
- पेस्सिमिस्टिक एस्टीमेटर का उपयोग करना:' कुछ स्तिथि में, मात्रा Q की स्पष्ट कंडीशनल अपेक्षा के लिए प्रॉक्सी के रूप में, उचित रूप से टाइट सीमा का उपयोग किया जाता है जिसे पेस्सिमिस्टिक एस्टीमेटर कहा जाता है। पेस्सिमिस्टिक एस्टीमेटर वर्तमान स्थिति का कार्य है। वर्तमान स्थिति को देखते हुए यह Q की कंडीशनल अपेक्षा के लिए ऊपरी (या निचला) होना चाहिए, और यह प्रयोग के प्रत्येक रेनडोमाइसड चरण के साथ अपेक्षा में गैर-बढ़ती (या गैर-घटती) होनी चाहिए। सामान्यतः, अच्छे पेस्सिमिस्टिक एस्टीमेटर की गणना मूल प्रमाण के तर्क को स्पष्ट रूप से विखंडित करके की जा सकती है।
कंडीशनल अपेक्षाओं का उपयोग करने वाला उदाहरण
यह उदाहरण कंडीशनल अपेक्षा का उपयोग करके मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक को प्रदर्शित करता है।
मैक्स-कट लेम्मा
किसी भी अप्रत्यक्ष ग्राफ़ (असतत गणित) G = (V, E) को देखते हुए, अधिकतम कट समस्या ग्राफ़ के प्रत्येक शीर्ष को दो रंगों (जैसे काले या सफेद) में से के साथ रंगना है जिससे किनारों की संख्या को अधिकतम किया जा सके जिनके अंतिम बिंदु हैं अलग - अलग रंग। (कहो ऐसी धार कटी है।)
'मैक्स-कट लेम्मा:' किसी भी ग्राफ G = (V, E) में, कम से कम |E|/2 किनारों को काटा जा सकता है।
'प्रोबबिलिस्टिक प्रमाण।' सफेद सिक्का उछालकर प्रत्येक शीर्ष को काला या सफेद रंग दें। गणना के अनुसार, E में किसी भी किनारे E के लिए, इसके कटने की संभावना 1/2 है। इस प्रकार, अपेक्षित मान या रैखिकता के अनुसार, काटे गए किनारों की अपेक्षित संख्या |E|/2 है। इस प्रकार, ऐसा रंग उपस्तिथ है जो कम से कम |E|/2 किनारों को क्यूईडी काटता है।
कंडीशनल अपेक्षाओं के साथ मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक
मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक को प्रयुक्त करने के लिए, पहले रेनडोमाइसड प्रयोग को छोटे रेनडोमाइसड चरणों के अनुक्रम के रूप में मॉडल किया जाता है। इस स्तिथि में प्रत्येक चरण को किसी विशेष शीर्ष के लिए रंग की चॉइस के रूप में मानना स्वाभाविक है (इसलिए |V| चरण हैं)।
इसके पश्चात , प्रत्येक चरण में रैंडम चॉइस को डेटरमिनिस्टिक चॉइस से परिवर्तन , जिससे विफलता की कंडीशनल प्रोबबिलिस्टिक को बनाए रखा जा सके, अब तक रंगे गए शीर्षों को 1 से नीचे दिया गया है। (यहां विफलता का अर्थ है कि अंततः |E|/2 से कम किनारे काटे गए हैं।)
इस स्तिथि में, विफलता की कंडीशनल प्रोबबिलिस्टिक की गणना करना सरल नहीं है। वास्तव में, मूल प्रमाण सीधे विफलता की संभावना की गणना नहीं करता था; इसके अतिरिक्त, प्रमाण ने यह दिखाकर कार्य किया कि कटे हुए किनारों की अपेक्षित संख्या कम से कम |ई|/2 थी।
माना रेनडोमाइसड वेरिएबल Q कटे हुए किनारों की संख्या है। विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखने के लिए, Q की कंडीशनल अपेक्षा को सीमा |E|/2 पर या उससे ऊपर रखना पर्याप्त है। (ऐसा इसलिए है क्योंकि जब तक Q की कंडीशनल अपेक्षा कम से कम |E|/2 है, तब तक कुछ अभी भी पहुंच योग्य परिणाम होना चाहिए जहां Q कम से कम |E|/2 है, इसलिए ऐसे परिणाम तक पहुंचने की कंडीशनल प्रोबबिलिस्टिक धनात्मक है।) Q की कंडीशनल अपेक्षा को |E|/2 या उससे ऊपर रखने के लिए, एल्गोरिदम, प्रत्येक चरण में, विचाराधीन शीर्ष को रंग देगा जिससे Q की परिणामी कंडीशनल अपेक्षा को अधिकतम किया जा सकता है। यह पर्याप्त है, क्योंकि कुछ चाइल्ड होंगे जिनकी कंडीशनल अपेक्षा कम से कम वर्तमान स्थिति है की कंडीशनल अपेक्षा (और इस प्रकार कम से कम |ई|/2)।
यह देखते हुए कि कुछ शीर्ष पहले से ही रंगीन हैं, यह कंडीशनल अपेक्षा क्या है? मूल प्रमाण के तर्क के पश्चात, कटे हुए किनारों की संख्या की कंडीशनल अपेक्षा है
- किनारों की संख्या जिनके अंतिम बिंदु अब तक भिन्न-भिन्न रंग के हैं
- + (1/2)*(कम से कम समापन बिंदु वाले किनारों की संख्या जो अभी तक रंगीन नहीं हुई है)।
एल्गोरिथम
इस प्रकार से उपरोक्त कंडीशनल अपेक्षा के परिणामी मूल्य को अधिकतम करने के लिए एल्गोरिदम प्रत्येक शीर्ष को रंग देता है। यह कंडीशनल अपेक्षा को |ई|/2 या उससे ऊपर रखने की प्रमाण है, और इसलिए विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखने की प्रमाण है, जो परिवर्तन में सफल परिणाम की प्रमाण देता है। और गणना द्वारा, एल्गोरिथ्म निम्नलिखित को सरल बनाता है:
1. V में प्रत्येक शीर्ष u के लिए (किसी भी क्रम में): 2. आप के पूर्व से ही रंगीन निकटतम शीर्षों पर विचार करें। 3. इन शीर्षों में यदि सफेद से अधिक काले हैं तो आपको सफेद रंग दें। 4. नहीं तो तुम्हें काला रंग प्राप्त होगा.
इसकी व्युत्पत्ति के कारण, यह डेटरमिनिस्टिक एल्गोरिदम दिए गए ग्राफ़ के कम से कम आधे किनारों को काटने की प्रमाण देता है। (यह इसे मैक्स-कट के लिए अधिकतम कट या अप्प्रोक्सीमेसन एल्गोरिदम 0.5-अप्प्रोक्सीमेसन एल्गोरिदम बनाता है।)
पेस्सिमिस्टिक एस्टीमेटरों का उपयोग करने वाला उदाहरण
इसके प्रकार से उदाहरण पेस्सिमिस्टिक एस्टीमेटरों के उपयोग को दर्शाता है।
तुरान का प्रमेय
तुरान के प्रमेय को बताने का विधि निम्नलिखित है:
- किसी भी ग्राफ G = (V, E) में कम से कम |V|/(D+1) आकार का स्वतंत्र समुच्चय (ग्राफ सिद्धांत) होता है, जहां D = 2|E|/|V| ग्राफ़ की औसत डिग्री है.
तुरान के प्रमेय का प्रोबबिलिस्टिक प्रमाण
एक स्वतंत्र समुच्चय S के निर्माण के लिए निम्नलिखित रेनडोमाइसड प्रक्रिया पर विचार करें:
1. रिक्त समुच्चय होने के लिए S को आरंभ करें। 2. V में प्रत्येक शीर्ष u के लिए रेनडोमाइसड क्रम में: 3. यदि आपका कोई निकटतम S में नहीं है, तो S में u जोड़ें 4. वापसी एस.
स्पष्ट रूप से प्रक्रिया स्वतंत्र समुच्चय की गणना करती है। कोई भी शीर्ष u जिसे उसके सभी निकटतम से पहले माना जाता है, उसे S में जोड़ा जाएगा। इस प्रकार, d(u) को u की डिग्री को निरूपित करने पर, संभावना है कि u को S में जोड़ा जाता है, कम से कम 1/(d(u)+1) है ). अपेक्षित मान या रैखिकता के अनुसार, S का अपेक्षित आकार कम से कम है
(उपरोक्त असमानता इस प्रकार है क्योंकि 1/(x+1) x में उत्तल फलन है, इसलिए बाईं ओर को न्यूनतम किया जाता है, बनियम कि डिग्री का योग 2|E| पर तय किया जाए, जब प्रत्येक d(u) = डी = 2|ई|/|वी|.) प्रश्न
पेस्सिमिस्टिक एस्टीमेटरों का उपयोग करके मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक
इस स्तिथि में, रेनडोमाइसड प्रक्रिया में |V| है पद। प्रत्येक चरण कुछ ऐसे शीर्षों पर विचार करता है जिन्हें अभी तक नहीं माना गया है और यदि उसके किसी भी निकटतम को अभी तक नहीं जोड़ा गया है तो उसे एस में जोड़ दिया जाता है। मान लें कि रेनडोमाइसड वेरिएबल Q, S में जोड़े गए शीर्षों की संख्या है। प्रमाण से पता चलता है कि E[Q] ≥ |V|/(D+1)।
हम प्रत्येक रेनडोमाइसड चरण को डेटरमिनिस्टिक चरण से प्रतिस्थापित करेंगे जो Q की कंडीशनल अपेक्षा को |V|/(D+1) पर या उससे ऊपर रखता है। यह सफल परिणाम सुनिश्चित करेगा, अर्थात, जिसमें स्वतंत्र समुच्चय S का आकार कम से कम |V|/(D+1) हो, जो तुरान के प्रमेय में सीमा को साकार करता है।
यह देखते हुए कि प्रथम t पद उठाया जा चुका है, मान लीजिए S(t)अब तक जोड़े गए शीर्षों को दर्शाता है। जब R(t) उन शीर्षों को दर्शाता है जिन पर अभी तक विचार नहीं किया गया है, और जिनका S(t) में कोई निकटतम नहीं है. पहले t चरणों को देखते हुए, मूल प्रमाण में तर्क के पश्चात, R(t) में कोई भी शीर्ष w दिया गया है में S में जोड़े जाने की कंडीशनल प्रोबबिलिस्टिक कम से कम 1/(d(w)+1) है, इसलिए Q की कंडीशनल अपेक्षा कम से कम है
मान लीजिये Q(t) उपर्युक्त मात्रा को दर्शाता है, जिसे कंडीशनल अपेक्षा के लिए पेस्सिमिस्टिक एस्टीमेटर' कहा जाता है।
प्रमाण से पता चला कि पेस्सिमिस्टिक एस्टीमेटर प्रारंभ में कम से कम |V|/(D+1) है। (अर्थात्, Q(0) ≥ |V|/(D+1).) एल्गोरिदम पेस्सिमिस्टिक एस्टीमेटर को घटने से रोकने के लिए प्रत्येक विकल्प चुनेगा, अर्थात, जिससे Q(t+1) ≥ Q(t) प्रत्येक t के लिए। चूँकि पेस्सिमिस्टिक एस्टीमेटर कंडीशनल अपेक्षा पर निचली सीमा रखता है, यह सुनिश्चित करेगा कि कंडीशनल अपेक्षा |V|/(D+1) से ऊपर रहे, जो परिवर्तन में यह सुनिश्चित करेगा कि विफलता की कंडीशनल प्रोबबिलिस्टिक 1 से नीचे रहे है।
मान लीजिए कि आप अगले ((t+1)-st) चरण में एल्गोरिथम द्वारा माना गया शीर्ष है।
यदि आपका पहले से ही S में कोई निकटतम है, तो आपको S में नहीं जोड़ा जाता है और (Q(t) के निरीक्षण द्वारा)), पेस्सिमिस्टिक एस्टीमेटर अपरिवर्तित है। यदि S में u का कोई निकटतम नहीं है, तब S में u जोड़ा जाता है।
गणना के अनुसार, यदि u को शेष शीर्षों से रेनडोमाइसड रूप से चुना जाता है, तो पेस्सिमिस्टिक एस्टीमेटर में अपेक्षित वृद्धि गैर-ऋणात्मक है। ['गणना के अनुसार।' R(t) में शीर्ष चुनने पर नियम , पेस्सिमिस्टिक एस्टीमेटर में दिए गए पद 1/(d(w)+1) को योग से हटा दिए जाने की संभावना अधिकतम (d(w)+1)/|R(t)| है, इसलिए योग में प्रत्येक पद में अपेक्षित कमी अधिकतम 1/|R(t)| है. जहाँ R(t)) योग में नियम इस प्रकार, योग में अपेक्षित कमी अधिकतम 1 है। इस मध्य, S का आकार 1 बढ़ जाता है।]
इस प्रकार, आपके पास कुछ विकल्प उपस्तिथ होने चाहिए जो पेस्सिमिस्टिक एस्टीमेटर को कम होने से रोकते हैं।
पेस्सिमिस्टिक एस्टीमेटर को अधिकतम करने वाला एल्गोरिदम
परिणामी पेस्सिमिस्टिक एस्टीमेटर को अधिकतम करने के लिए नीचे दिया गया एल्गोरिदम प्रत्येक शीर्ष u को चुनता है। पिछले विचारों के अनुसार, यह पेस्सिमिस्टिक एस्टीमेटर को कम होने से रोकता है और सफल परिणाम की प्रमाण देता है।
नीचे, N(t)(u) R(t) में u के निकटतम को दर्शाता है (अर्थात, आपके ऐसे निकटतम जो न तो S में हैं और न ही S में उनका कोई निकटतम है)।
1. रिक्त समुच्चय होने के लिए S को आरंभ करें।
2. जबकि एस में कोई निकटतम नहीं होने के कारण अभी तक नहीं माना जाने वाला शीर्ष u उपस्तिथ है:
3. S में ऐसा शीर्ष u जोड़ें जहां u न्यूनतम हो .
4. वापसी S.
एल्गोरिदम जो पेस्सिमिस्टिक एस्टीमेटर को अधिकतम नहीं करते
मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक के कार्य करने के लिए, यह पर्याप्त है यदि एल्गोरिदम पेस्सिमिस्टिक एस्टीमेटर को घटने (या बढ़ने, जैसा उपयुक्त हो) से रखता है। एल्गोरिदम को पेस्सिमिस्टिक एस्टीमेटर को अधिकतम (या न्यूनतम) करना आवश्यक नहीं है। यह एल्गोरिदम प्राप्त करने में कुछ लचीलापन देता है। इसके अतिरिक्त दो एल्गोरिदम इसे दर्शाते हैं।
1. रिक्त समुच्चय होने के लिए S को आरंभ करें। 2. जबकि ग्राफ़ में शीर्ष u उपस्तिथ है जिसका S में कोई निकटतम नहीं है: 3. S में ऐसा शीर्ष u जोड़ें, जहां u, d(u) (u की प्रारंभिक डिग्री) को न्यूनतम करता है। 4. वापसी एस.
1. रिक्त समुच्चय होने के लिए S को आरंभ करें। 2. जबकि शेष ग्राफ रिक्त नहीं है: 3. S में शीर्ष u जोड़ें, जहां शेष ग्राफ़ में u की न्यूनतम डिग्री है। 4. ग्राफ़ से आप और उसके सभी निकटतम को हटा दें। 5. वापसी S.
प्रत्येक एल्गोरिदम का विश्लेषण पहले की तरह ही पेस्सिमिस्टिक एस्टीमेटर के साथ किया जाता है। किसी भी एल्गोरिदम के प्रत्येक चरण के साथ, पेस्सिमिस्टिक एस्टीमेटर में शुद्ध वृद्धि होती है
जहां N(t)(u) शेष ग्राफ़ में u के निकटतम को दर्शाता है (अर्थात, R(t) में)।.
प्रथम एल्गोरिदम के लिए, शुद्ध वृद्धि गैर-ऋणात्मक है क्योंकि, u की चॉइस से,
- ,
जहां d(u) मूल ग्राफ़ में u की डिग्री है।
दूसरे एल्गोरिदम के लिए, शुद्ध वृद्धि गैर-ऋणात्मक है क्योंकि, u की चॉइस से,
- ,
जहां d′(u) शेष ग्राफ़ में u की डिग्री है।
यह भी देखें
- प्रोबबिलिस्टिक मेथड
- डेरनडोमाईज़ेसन
- रेनडोमाइसड राउंडिंग
संदर्भ
- Raghavan, Prabhakar (1988), "Probabilistic construction of deterministic algorithms: approximating packing integer programs", Journal of Computer and System Sciences, 37 (2): 130–143, doi:10.1016/0022-0000(88)90003-7.
अग्रिम पठन
- Alon, Noga; Spencer, Joel (2008). The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization (Third ed.). Hoboken, NJ: John Wiley and Sons. pp. 250 et seq. ISBN 978-0-470-17020-5. MR 2437651. (cited pages in 2nd edition, ISBN 9780471653981)
- Motwani, Rajeev; Raghavan, Prabhakar (25 August 1995). Randomized algorithms. Cambridge University Press. pp. 120–. ISBN 978-0-521-47465-8.
- Vazirani, Vijay (5 December 2002), Approximation algorithms, Springer Verlag, pp. 130–, ISBN 978-3-540-65367-7
बाहरी संबंध
- The probabilistic method — method of conditional probabilities, blog entry by Neal E. Young, accessed 19/04/2012.
