सशर्त संभावनाओं की विधि: Difference between revisions
(Created page with "गणित और कंप्यूटर विज्ञान में, वांछित संयोजक गुणों के साथ गणितीय व...") |
No edit summary |
||
| Line 1: | Line 1: | ||
गणित और [[कंप्यूटर विज्ञान]] में, वांछित संयोजक गुणों के साथ गणितीय वस्तुओं के अस्तित्व को साबित करने के लिए संभाव्य पद्धति का उपयोग किया जाता है। प्रमाण संभाव्य हैं - वे यह दिखाकर काम करते हैं कि कुछ संभाव्यता वितरण से चुनी गई | गणित और [[कंप्यूटर विज्ञान]] में, वांछित संयोजक गुणों के साथ गणितीय वस्तुओं के अस्तित्व को साबित करने के लिए संभाव्य पद्धति का उपयोग किया जाता है। प्रमाण संभाव्य हैं - वे यह दिखाकर काम करते हैं कि कुछ संभाव्यता वितरण से चुनी गई यादृच्छिक वस्तु में सकारात्मक संभावना के साथ वांछित गुण होते हैं। नतीजतन, वे गैर-रचनात्मक प्रमाण हैं - वे वांछित वस्तुओं की गणना के लिए कुशल विधि का स्पष्ट रूप से वर्णन नहीं करते हैं। | ||
सशर्त संभावनाओं की विधि {{harv|Spencer|1987}}, {{harv|Raghavan|1988}} ऐसे प्रमाण को, बहुत सटीक अर्थ में, | सशर्त संभावनाओं की विधि {{harv|Spencer|1987}}, {{harv|Raghavan|1988}} ऐसे प्रमाण को, बहुत सटीक अर्थ में, कुशल नियतात्मक एल्गोरिदम में परिवर्तित करता है, जो वांछित गुणों के साथ किसी वस्तु की गणना करने की गारंटी देता है। यानी विधि यादृच्छिकीकरण प्रमाण. मूल विचार यादृच्छिक प्रयोग में प्रत्येक यादृच्छिक विकल्प को नियतात्मक विकल्प से प्रतिस्थापित करना है, ताकि अब तक के विकल्पों को देखते हुए विफलता की सशर्त संभावना को 1 से नीचे रखा जा सके। | ||
यह विधि यादृच्छिक राउंडिंग के संदर्भ में विशेष रूप से प्रासंगिक है (जो सन्निकटन एल्गोरिदम को डिजाइन करने के लिए संभाव्य विधि का उपयोग करती है)। | यह विधि यादृच्छिक राउंडिंग के संदर्भ में विशेष रूप से प्रासंगिक है (जो सन्निकटन एल्गोरिदम को डिजाइन करने के लिए संभाव्य विधि का उपयोग करती है)। | ||
| Line 10: | Line 10: | ||
{{harv|Raghavan|1988}} यह विवरण देता है: | {{harv|Raghavan|1988}} यह विवरण देता है: | ||
: हम पहले संभाव्य विधि का उपयोग करके | : हम पहले संभाव्य विधि का उपयोग करके सिद्ध रूप से अच्छे अनुमानित समाधान के अस्तित्व को दिखाते हैं... [फिर हम] दिखाते हैं कि संभाव्य अस्तित्व प्रमाण को, बहुत सटीक अर्थ में, नियतात्मक सन्निकटन एल्गोरिदम में परिवर्तित किया जा सकता है। | ||
(राघवन यादृच्छिक पूर्णांकन के संदर्भ में विधि पर चर्चा कर रहे हैं, लेकिन यह सामान्य रूप से संभाव्य विधि के साथ काम करता है।) | (राघवन यादृच्छिक पूर्णांकन के संदर्भ में विधि पर चर्चा कर रहे हैं, लेकिन यह सामान्य रूप से संभाव्य विधि के साथ काम करता है।) | ||
[[File:Method of conditional probabilities.png|thumb|450px|right|सशर्त संभावनाओं की विधि]]विधि को संभाव्य प्रमाण पर लागू करने के लिए, प्रमाण में यादृच्छिक रूप से चुनी गई वस्तु को | [[File:Method of conditional probabilities.png|thumb|450px|right|सशर्त संभावनाओं की विधि]]विधि को संभाव्य प्रमाण पर लागू करने के लिए, प्रमाण में यादृच्छिक रूप से चुनी गई वस्तु को यादृच्छिक प्रयोग द्वारा चुना जाना चाहिए जिसमें छोटे यादृच्छिक विकल्पों का अनुक्रम शामिल हो। | ||
सिद्धांत को स्पष्ट करने के लिए यहां | सिद्धांत को स्पष्ट करने के लिए यहां छोटा सा उदाहरण दिया गया है। | ||
: लेम्मा: ''तीन सिक्कों को उछालना संभव है ताकि पूंछों की संख्या कम से कम 2 हो।'' | : लेम्मा: ''तीन सिक्कों को उछालना संभव है ताकि पूंछों की संख्या कम से कम 2 हो।'' | ||
: ''संभाव्य प्रमाण।'' यदि तीन सिक्कों को यादृच्छिक रूप से उछाला जाता है, तो पूंछों की अपेक्षित संख्या 1.5 है। इस प्रकार, कुछ परिणाम (सिक्के उछालने का तरीका) होना चाहिए ताकि पूंछों की संख्या कम से कम 1.5 हो। चूँकि पूँछों की संख्या | : ''संभाव्य प्रमाण।'' यदि तीन सिक्कों को यादृच्छिक रूप से उछाला जाता है, तो पूंछों की अपेक्षित संख्या 1.5 है। इस प्रकार, कुछ परिणाम (सिक्के उछालने का तरीका) होना चाहिए ताकि पूंछों की संख्या कम से कम 1.5 हो। चूँकि पूँछों की संख्या पूर्णांक है, ऐसे परिणाम में कम से कम 2 पूँछें होती हैं। ''प्रश्न'' | ||
इस उदाहरण में यादृच्छिक प्रयोग में तीन निष्पक्ष सिक्कों को उछालना शामिल है। प्रयोग को आसन्न चित्र में जड़ वाले पेड़ द्वारा दर्शाया गया है। आठ परिणाम हैं, प्रत्येक पेड़ में | इस उदाहरण में यादृच्छिक प्रयोग में तीन निष्पक्ष सिक्कों को उछालना शामिल है। प्रयोग को आसन्न चित्र में जड़ वाले पेड़ द्वारा दर्शाया गया है। आठ परिणाम हैं, प्रत्येक पेड़ में पत्ते के अनुरूप है। यादृच्छिक प्रयोग का परीक्षण जड़ (पेड़ में शीर्ष नोड, जहां कोई सिक्का नहीं उछाला गया है) से पत्ते तक यादृच्छिक चलने से मेल खाता है। सफल परिणाम वे हैं जिनमें कम से कम दो सिक्के पीछे आए। पेड़ में आंतरिक नोड्स आंशिक रूप से निर्धारित परिणामों के अनुरूप हैं, जहां अब तक केवल 0, 1, या 2 सिक्के ही उछाले गए हैं। | ||
सशर्त संभावनाओं की पद्धति को लागू करने के लिए, जैसे-जैसे प्रयोग चरण दर चरण आगे बढ़ता है, ''अब तक के विकल्पों को देखते हुए विफलता की सशर्त संभावना'' पर ध्यान केंद्रित किया जाता है। | सशर्त संभावनाओं की पद्धति को लागू करने के लिए, जैसे-जैसे प्रयोग चरण दर चरण आगे बढ़ता है, ''अब तक के विकल्पों को देखते हुए विफलता की सशर्त संभावना'' पर ध्यान केंद्रित किया जाता है। | ||
| Line 30: | Line 30: | ||
:: ''वर्तमान स्थिति को देखते हुए विफलता की सशर्त संभावना 1 से कम है।'' | :: ''वर्तमान स्थिति को देखते हुए विफलता की सशर्त संभावना 1 से कम है।'' | ||
इस तरह, लेबल 0 वाले पत्ते पर पहुंचने की गारंटी है, यानी | इस तरह, लेबल 0 वाले पत्ते पर पहुंचने की गारंटी है, यानी सफल परिणाम। | ||
अपरिवर्तनीय प्रारंभ में (मूल पर) कायम रहता है, क्योंकि मूल प्रमाण से पता चला है कि विफलता की (बिना शर्त) संभावना 1 से कम है। किसी भी आंतरिक नोड पर सशर्त संभावना उसके बच्चों की सशर्त संभावनाओं का औसत है। बाद वाली संपत्ति महत्वपूर्ण है क्योंकि इसका तात्पर्य है कि ''किसी भी आंतरिक नोड जिसकी सशर्त संभावना 1 से कम है, में कम से कम | अपरिवर्तनीय प्रारंभ में (मूल पर) कायम रहता है, क्योंकि मूल प्रमाण से पता चला है कि विफलता की (बिना शर्त) संभावना 1 से कम है। किसी भी आंतरिक नोड पर सशर्त संभावना उसके बच्चों की सशर्त संभावनाओं का औसत है। बाद वाली संपत्ति महत्वपूर्ण है क्योंकि इसका तात्पर्य है कि ''किसी भी आंतरिक नोड जिसकी सशर्त संभावना 1 से कम है, में कम से कम बच्चा है जिसकी सशर्त संभावना 1 से कम है।'' इस प्रकार, किसी भी आंतरिक नोड से, कोई हमेशा कुछ बच्चे को चुन सकता है ताकि अपरिवर्तनीय को बनाए रखा जा सके। चूँकि अंत में अपरिवर्तनीयता कायम रहती है, जब चलना पत्ते पर पहुँचता है और सभी विकल्प निर्धारित हो चुके होते हैं, तो इस तरह से पहुँचा गया परिणाम सफल होना चाहिए। | ||
== दक्षता == | == दक्षता == | ||
विधि के | विधि के विशिष्ट अनुप्रयोग में, लक्ष्य उचित रूप से कुशल एल्गोरिदम द्वारा परिणामी नियतात्मक प्रक्रिया को कार्यान्वित करने में सक्षम होना है (कुशल शब्द का आमतौर पर एल्गोरिदम होता है जो बहुपद समय में चलता है), भले ही आमतौर पर संभावित परिणामों की संख्या बहुत बड़ी हो (घातीय रूप से बड़ा)। उदाहरण के लिए, सिक्का उछालने के कार्य पर विचार करें, लेकिन बड़े n के लिए इसे n फ्लिप तक विस्तारित किया गया है। | ||
आदर्श स्थिति में, आंशिक स्थिति (पेड़ में | आदर्श स्थिति में, आंशिक स्थिति (पेड़ में नोड) को देखते हुए, विफलता की सशर्त संभावना (नोड पर लेबल) की गणना कुशलतापूर्वक और सटीक रूप से की जा सकती है। (उपर्युक्त उदाहरण इस प्रकार है।) यदि ऐसा है, तो एल्गोरिदम वर्तमान नोड के प्रत्येक बच्चे पर सशर्त संभावनाओं की गणना करके अगले नोड का चयन कर सकता है, फिर किसी भी बच्चे पर जा सकता है जिसकी सशर्त संभावना कम है 1 से अधिक। जैसा कि ऊपर चर्चा की गई है, ऐसे नोड होने की गारंटी है। | ||
दुर्भाग्य से, अधिकांश अनुप्रयोगों में, विफलता की सशर्त संभावना की कुशलता से गणना करना आसान नहीं है। इससे निपटने के लिए दो मानक और संबंधित तकनीकें हैं: | दुर्भाग्य से, अधिकांश अनुप्रयोगों में, विफलता की सशर्त संभावना की कुशलता से गणना करना आसान नहीं है। इससे निपटने के लिए दो मानक और संबंधित तकनीकें हैं: | ||
* 'सशर्त अपेक्षा का उपयोग करना:' कई संभाव्य प्रमाण इस प्रकार काम करते हैं: वे स्पष्ट रूप से | * 'सशर्त अपेक्षा का उपयोग करना:' कई संभाव्य प्रमाण इस प्रकार काम करते हैं: वे स्पष्ट रूप से यादृच्छिक चर Q को परिभाषित करते हैं, दिखाते हैं कि (i) Q की अपेक्षा अधिकतम (या कम से कम) कुछ सीमा मूल्य है, और (ii) किसी भी परिणाम जहां Q अधिकतम (कम से कम) इस सीमा पर है, परिणाम सफल है। तब (i) का अर्थ है कि परिणाम मौजूद है जहां Q अधिकतम (कम से कम) सीमा है, और इसका और (ii) का अर्थ है कि सफल परिणाम है। (उपरोक्त उदाहरण में, क्यू पूंछों की संख्या है, जो कम से कम सीमा 1.5 होनी चाहिए। कई अनुप्रयोगों में, क्यू किसी दिए गए परिणाम में होने वाली बुरी घटनाओं (जरूरी नहीं कि असंबद्ध) की संख्या है, जहां प्रत्येक बुरी घटना मेल खाती है तरह से प्रयोग विफल हो सकता है, और घटित होने वाली बुरी घटनाओं की अपेक्षित संख्या 1 से कम है।) | ||
इस मामले में, विफलता की सशर्त संभावना को 1 से नीचे रखने के लिए, Q की सशर्त अपेक्षा को सीमा से नीचे (या ऊपर) रखना पर्याप्त है। ऐसा करने के लिए, विफलता की सशर्त संभावना की गणना करने के बजाय, एल्गोरिदम क्यू की सशर्त अपेक्षा की गणना करता है और तदनुसार आगे बढ़ता है: प्रत्येक आंतरिक नोड पर, कुछ बच्चे होते हैं जिनकी सशर्त अपेक्षा अधिकतम (कम से कम) नोड की सशर्त अपेक्षा होती है; एल्गोरिथ्म वर्तमान नोड से ऐसे बच्चे की ओर बढ़ता है, इस प्रकार सशर्त अपेक्षा को सीमा से नीचे (ऊपर) रखता है। | इस मामले में, विफलता की सशर्त संभावना को 1 से नीचे रखने के लिए, Q की सशर्त अपेक्षा को सीमा से नीचे (या ऊपर) रखना पर्याप्त है। ऐसा करने के लिए, विफलता की सशर्त संभावना की गणना करने के बजाय, एल्गोरिदम क्यू की सशर्त अपेक्षा की गणना करता है और तदनुसार आगे बढ़ता है: प्रत्येक आंतरिक नोड पर, कुछ बच्चे होते हैं जिनकी सशर्त अपेक्षा अधिकतम (कम से कम) नोड की सशर्त अपेक्षा होती है; एल्गोरिथ्म वर्तमान नोड से ऐसे बच्चे की ओर बढ़ता है, इस प्रकार सशर्त अपेक्षा को सीमा से नीचे (ऊपर) रखता है। | ||
* 'निराशावादी अनुमानक का उपयोग करना:' कुछ मामलों में, मात्रा Q की सटीक सशर्त अपेक्षा के लिए | * 'निराशावादी अनुमानक का उपयोग करना:' कुछ मामलों में, मात्रा Q की सटीक सशर्त अपेक्षा के लिए प्रॉक्सी के रूप में, उचित रूप से तंग सीमा का उपयोग किया जाता है जिसे निराशावादी अनुमानक कहा जाता है। निराशावादी अनुमानक वर्तमान स्थिति का कार्य है। वर्तमान स्थिति को देखते हुए यह Q की सशर्त अपेक्षा के लिए ऊपरी (या निचला) होना चाहिए, और यह प्रयोग के प्रत्येक यादृच्छिक चरण के साथ अपेक्षा में गैर-बढ़ती (या गैर-घटती) होनी चाहिए। आमतौर पर, अच्छे निराशावादी अनुमानक की गणना मूल प्रमाण के तर्क को सटीक रूप से विखंडित करके की जा सकती है। | ||
== सशर्त अपेक्षाओं का उपयोग करने वाला उदाहरण == | == सशर्त अपेक्षाओं का उपयोग करने वाला उदाहरण == | ||
| Line 54: | Line 54: | ||
=== मैक्स-कट लेम्मा === | === मैक्स-कट लेम्मा === | ||
किसी भी अप्रत्यक्ष ग्राफ़ (असतत गणित) जी = (वी, ई) को देखते हुए, [[अधिकतम कटौती]] समस्या ग्राफ़ के प्रत्येक शीर्ष को दो रंगों (जैसे काले या सफेद) में से | किसी भी अप्रत्यक्ष ग्राफ़ (असतत गणित) जी = (वी, ई) को देखते हुए, [[अधिकतम कटौती]] समस्या ग्राफ़ के प्रत्येक शीर्ष को दो रंगों (जैसे काले या सफेद) में से के साथ रंगना है ताकि किनारों की संख्या को अधिकतम किया जा सके जिनके अंतिम बिंदु हैं अलग - अलग रंग। (कहो ऐसी धार कटी है।) | ||
'मैक्स-कट लेम्मा:' किसी भी ग्राफ G = (V, E) में, कम से कम |E|/2 किनारों को काटा जा सकता है। | 'मैक्स-कट लेम्मा:' किसी भी ग्राफ G = (V, E) में, कम से कम |E|/2 किनारों को काटा जा सकता है। | ||
'संभाव्य प्रमाण।' गोरा सिक्का उछालकर प्रत्येक शीर्ष को काला या सफेद रंग दें। गणना के अनुसार, ई में किसी भी किनारे ई के लिए, इसके कटने की संभावना 1/2 है। इस प्रकार, अपेक्षित मान#रैखिकता के अनुसार, काटे गए किनारों की अपेक्षित संख्या |E|/2 है। इस प्रकार, ऐसा रंग मौजूद है जो कम से कम |E|/2 किनारों को काटता है। QED | |||
=== सशर्त अपेक्षाओं के साथ सशर्त संभावनाओं की विधि === | === सशर्त अपेक्षाओं के साथ सशर्त संभावनाओं की विधि === | ||
| Line 73: | Line 73: | ||
:: किनारों की संख्या जिनके अंतिम बिंदु अब तक अलग-अलग रंग के हैं | :: किनारों की संख्या जिनके अंतिम बिंदु अब तक अलग-अलग रंग के हैं | ||
:: + (1/2)*(कम से कम | :: + (1/2)*(कम से कम समापन बिंदु वाले किनारों की संख्या जो अभी तक रंगीन नहीं हुई है)। | ||
=== एल्गोरिथम === | === एल्गोरिथम === | ||
उपरोक्त सशर्त अपेक्षा के परिणामी मूल्य को अधिकतम करने के लिए एल्गोरिदम प्रत्येक शीर्ष को रंग देता है। यह सशर्त अपेक्षा को |ई|/2 या उससे ऊपर रखने की गारंटी है, और इसलिए विफलता की सशर्त संभावना को 1 से नीचे रखने की गारंटी है, जो बदले में | उपरोक्त सशर्त अपेक्षा के परिणामी मूल्य को अधिकतम करने के लिए एल्गोरिदम प्रत्येक शीर्ष को रंग देता है। यह सशर्त अपेक्षा को |ई|/2 या उससे ऊपर रखने की गारंटी है, और इसलिए विफलता की सशर्त संभावना को 1 से नीचे रखने की गारंटी है, जो बदले में सफल परिणाम की गारंटी देता है। गणना द्वारा, एल्गोरिथ्म निम्नलिखित को सरल बनाता है: | ||
1. वी में प्रत्येक शीर्ष यू के लिए (किसी भी क्रम में): | 1. वी में प्रत्येक शीर्ष यू के लिए (किसी भी क्रम में): | ||
| Line 90: | Line 90: | ||
अगला उदाहरण निराशावादी अनुमानकों के उपयोग को दर्शाता है। | अगला उदाहरण निराशावादी अनुमानकों के उपयोग को दर्शाता है। | ||
=== तुरान का प्रमेय | === तुरान का प्रमेय === | ||
तुरान के प्रमेय को बताने का | तुरान के प्रमेय को बताने का तरीका निम्नलिखित है: | ||
: किसी भी ग्राफ G = (V, E) में कम से कम |V|/(D+1) आकार का | : किसी भी ग्राफ G = (V, E) में कम से कम |V|/(D+1) आकार का स्वतंत्र सेट (ग्राफ सिद्धांत) होता है, जहां D = 2|E|/|V| ग्राफ़ की औसत डिग्री है. | ||
=== तुरान के प्रमेय का संभाव्य प्रमाण === | === तुरान के प्रमेय का संभाव्य प्रमाण === | ||
| Line 103: | Line 103: | ||
3. यदि आपका कोई पड़ोसी S में नहीं है, तो S में u जोड़ें | 3. यदि आपका कोई पड़ोसी S में नहीं है, तो S में u जोड़ें | ||
4. वापसी एस. | 4. वापसी एस. | ||
स्पष्ट रूप से प्रक्रिया | स्पष्ट रूप से प्रक्रिया स्वतंत्र सेट की गणना करती है। कोई भी शीर्ष u जिसे उसके सभी पड़ोसियों से पहले माना जाता है, उसे S में जोड़ा जाएगा। इस प्रकार, d(u) को u की डिग्री को निरूपित करने पर, संभावना है कि u को S में जोड़ा जाता है, कम से कम 1/(d(u)+1) है ). अपेक्षित मान#रैखिकता के अनुसार, S का अपेक्षित आकार कम से कम है | ||
: <math>\sum_{u\in V} \frac{1}{d(u)+1} ~\ge~\frac{|V|}{D+1}.</math> | : <math>\sum_{u\in V} \frac{1}{d(u)+1} ~\ge~\frac{|V|}{D+1}.</math> | ||
| Line 112: | Line 112: | ||
इस मामले में, यादृच्छिक प्रक्रिया में |V| है कदम। प्रत्येक चरण कुछ ऐसे शीर्षों पर विचार करता है जिन्हें अभी तक नहीं माना गया है और यदि उसके किसी भी पड़ोसी को अभी तक नहीं जोड़ा गया है तो उसे एस में जोड़ दिया जाता है। मान लें कि यादृच्छिक चर Q, S में जोड़े गए शीर्षों की संख्या है। प्रमाण से पता चलता है कि E[Q] ≥ |V|/(D+1)। | इस मामले में, यादृच्छिक प्रक्रिया में |V| है कदम। प्रत्येक चरण कुछ ऐसे शीर्षों पर विचार करता है जिन्हें अभी तक नहीं माना गया है और यदि उसके किसी भी पड़ोसी को अभी तक नहीं जोड़ा गया है तो उसे एस में जोड़ दिया जाता है। मान लें कि यादृच्छिक चर Q, S में जोड़े गए शीर्षों की संख्या है। प्रमाण से पता चलता है कि E[Q] ≥ |V|/(D+1)। | ||
हम प्रत्येक यादृच्छिक चरण को | हम प्रत्येक यादृच्छिक चरण को नियतात्मक चरण से प्रतिस्थापित करेंगे जो Q की सशर्त अपेक्षा को |V|/(D+1) पर या उससे ऊपर रखता है। यह सफल परिणाम सुनिश्चित करेगा, अर्थात, जिसमें स्वतंत्र सेट S का आकार कम से कम |V|/(D+1) हो, जो तुरान के प्रमेय में सीमा को साकार करता है। | ||
यह देखते हुए कि पहला t कदम उठाया जा चुका है, मान लीजिए S<sup>(t)</sup>अब तक जोड़े गए शीर्षों को दर्शाता है। चलो आर<sup>(टी)</sup>उन शीर्षों को दर्शाता है जिन पर अभी तक विचार नहीं किया गया है, और जिनका एस में कोई पड़ोसी नहीं है<sup>(टी)</sup>. पहले t चरणों को देखते हुए, मूल प्रमाण में तर्क के बाद, R में कोई भी शीर्ष w दिया गया है<sup>(t)</sup> में S में जोड़े जाने की सशर्त संभावना कम से कम 1/(d(w)+1) है, इसलिए Q की सशर्त अपेक्षा कम से कम है | यह देखते हुए कि पहला t कदम उठाया जा चुका है, मान लीजिए S<sup>(t)</sup>अब तक जोड़े गए शीर्षों को दर्शाता है। चलो आर<sup>(टी)</sup>उन शीर्षों को दर्शाता है जिन पर अभी तक विचार नहीं किया गया है, और जिनका एस में कोई पड़ोसी नहीं है<sup>(टी)</sup>. पहले t चरणों को देखते हुए, मूल प्रमाण में तर्क के बाद, R में कोई भी शीर्ष w दिया गया है<sup>(t)</sup> में S में जोड़े जाने की सशर्त संभावना कम से कम 1/(d(w)+1) है, इसलिए Q की सशर्त अपेक्षा कम से कम है | ||
| Line 125: | Line 125: | ||
यदि आपका पहले से ही S में कोई पड़ोसी है, तो आपको S में नहीं जोड़ा जाता है और (Q के निरीक्षण द्वारा)<sup>(t)</sup>), निराशावादी अनुमानक अपरिवर्तित है। यदि S में u का कोई पड़ोसी नहीं है, तो S में u जोड़ा जाता है। | यदि आपका पहले से ही S में कोई पड़ोसी है, तो आपको S में नहीं जोड़ा जाता है और (Q के निरीक्षण द्वारा)<sup>(t)</sup>), निराशावादी अनुमानक अपरिवर्तित है। यदि S में u का कोई पड़ोसी नहीं है, तो S में u जोड़ा जाता है। | ||
गणना के अनुसार, यदि यू को शेष शीर्षों से यादृच्छिक रूप से चुना जाता है, तो निराशावादी अनुमानक में अपेक्षित वृद्धि गैर-नकारात्मक है। ['हिसाब।' आर में | गणना के अनुसार, यदि यू को शेष शीर्षों से यादृच्छिक रूप से चुना जाता है, तो निराशावादी अनुमानक में अपेक्षित वृद्धि गैर-नकारात्मक है। ['हिसाब।' आर में शीर्ष चुनने पर शर्त<sup>(टी)</sup>, निराशावादी अनुमानक में दिए गए पद 1/(d(w)+1) को योग से हटा दिए जाने की संभावना अधिकतम (d(w)+1)/|R है<sup>(टी)</sup>|, इसलिए योग में प्रत्येक पद में अपेक्षित कमी अधिकतम 1/|आर है<sup>(टी)</sup>|. आर हैं<sup>(t)</sup>योग में शर्तें। इस प्रकार, योग में अपेक्षित कमी अधिकतम 1 है। इस बीच, S का आकार 1 बढ़ जाता है।] | ||
इस प्रकार, आपके पास कुछ विकल्प मौजूद होने चाहिए जो निराशावादी अनुमानक को कम होने से रोकते हैं। | इस प्रकार, आपके पास कुछ विकल्प मौजूद होने चाहिए जो निराशावादी अनुमानक को कम होने से रोकते हैं। | ||
| Line 131: | Line 131: | ||
=== निराशावादी अनुमानक को अधिकतम करने वाला एल्गोरिदम === | === निराशावादी अनुमानक को अधिकतम करने वाला एल्गोरिदम === | ||
परिणामी निराशावादी अनुमानक को अधिकतम करने के लिए नीचे दिया गया एल्गोरिदम प्रत्येक शीर्ष यू को चुनता है। पिछले विचारों के अनुसार, यह निराशावादी अनुमानक को कम होने से रोकता है और | परिणामी निराशावादी अनुमानक को अधिकतम करने के लिए नीचे दिया गया एल्गोरिदम प्रत्येक शीर्ष यू को चुनता है। पिछले विचारों के अनुसार, यह निराशावादी अनुमानक को कम होने से रोकता है और सफल परिणाम की गारंटी देता है। | ||
नीचे, एन<sup>(t)</sup>(u) R में आपके पड़ोसियों को दर्शाता है<sup>(t)</sup> (अर्थात्, आपके पड़ोसी जो न तो S में हैं और न ही उनका कोई पड़ोसी S में है)। | नीचे, एन<sup>(t)</sup>(u) R में आपके पड़ोसियों को दर्शाता है<sup>(t)</sup> (अर्थात्, आपके पड़ोसी जो न तो S में हैं और न ही उनका कोई पड़ोसी S में है)। | ||
| Line 144: | Line 144: | ||
1. खाली सेट होने के लिए S को आरंभ करें। | 1. खाली सेट होने के लिए S को आरंभ करें। | ||
2. जबकि ग्राफ़ में | 2. जबकि ग्राफ़ में शीर्ष u मौजूद है जिसका S में कोई पड़ोसी नहीं है: | ||
3. S में ऐसा शीर्ष u जोड़ें, जहां u, d(u) (u की प्रारंभिक डिग्री) को न्यूनतम करता है। | 3. S में ऐसा शीर्ष u जोड़ें, जहां u, d(u) (u की प्रारंभिक डिग्री) को न्यूनतम करता है। | ||
4. वापसी एस. | 4. वापसी एस. | ||
| Line 150: | Line 150: | ||
1. खाली सेट होने के लिए S को आरंभ करें। | 1. खाली सेट होने के लिए S को आरंभ करें। | ||
2. जबकि शेष ग्राफ खाली नहीं है: | 2. जबकि शेष ग्राफ खाली नहीं है: | ||
3. S में | 3. S में शीर्ष u जोड़ें, जहां शेष ग्राफ़ में u की न्यूनतम डिग्री है। | ||
4. ग्राफ़ से आप और उसके सभी पड़ोसियों को हटा दें। | 4. ग्राफ़ से आप और उसके सभी पड़ोसियों को हटा दें। | ||
5. वापसी एस. | 5. वापसी एस. | ||
| Line 176: | Line 176: | ||
* व्युत्पत्तिकरण | * व्युत्पत्तिकरण | ||
* यादृच्छिक गोलाई | * यादृच्छिक गोलाई | ||
== संदर्भ == | == संदर्भ == | ||
| Line 239: | Line 237: | ||
| pages=130– | | pages=130– | ||
| isbn=978-3-540-65367-7}} | | isbn=978-3-540-65367-7}} | ||
== बाहरी संबंध == | == बाहरी संबंध == | ||
Revision as of 12:25, 3 August 2023
गणित और कंप्यूटर विज्ञान में, वांछित संयोजक गुणों के साथ गणितीय वस्तुओं के अस्तित्व को साबित करने के लिए संभाव्य पद्धति का उपयोग किया जाता है। प्रमाण संभाव्य हैं - वे यह दिखाकर काम करते हैं कि कुछ संभाव्यता वितरण से चुनी गई यादृच्छिक वस्तु में सकारात्मक संभावना के साथ वांछित गुण होते हैं। नतीजतन, वे गैर-रचनात्मक प्रमाण हैं - वे वांछित वस्तुओं की गणना के लिए कुशल विधि का स्पष्ट रूप से वर्णन नहीं करते हैं।
सशर्त संभावनाओं की विधि (Spencer 1987), (Raghavan 1988) ऐसे प्रमाण को, बहुत सटीक अर्थ में, कुशल नियतात्मक एल्गोरिदम में परिवर्तित करता है, जो वांछित गुणों के साथ किसी वस्तु की गणना करने की गारंटी देता है। यानी विधि यादृच्छिकीकरण प्रमाण. मूल विचार यादृच्छिक प्रयोग में प्रत्येक यादृच्छिक विकल्प को नियतात्मक विकल्प से प्रतिस्थापित करना है, ताकि अब तक के विकल्पों को देखते हुए विफलता की सशर्त संभावना को 1 से नीचे रखा जा सके।
यह विधि यादृच्छिक राउंडिंग के संदर्भ में विशेष रूप से प्रासंगिक है (जो सन्निकटन एल्गोरिदम को डिजाइन करने के लिए संभाव्य विधि का उपयोग करती है)।
सशर्त संभावनाओं की पद्धति को लागू करते समय, तकनीकी शब्द निराशावादी अनुमानक प्रमाण के अंतर्निहित वास्तविक सशर्त संभाव्यता (या सशर्त अपेक्षा) के स्थान पर उपयोग की जाने वाली मात्रा को संदर्भित करता है।
सिंहावलोकन
(Raghavan 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) का अर्थ है कि सफल परिणाम है। (उपरोक्त उदाहरण में, क्यू पूंछों की संख्या है, जो कम से कम सीमा 1.5 होनी चाहिए। कई अनुप्रयोगों में, क्यू किसी दिए गए परिणाम में होने वाली बुरी घटनाओं (जरूरी नहीं कि असंबद्ध) की संख्या है, जहां प्रत्येक बुरी घटना मेल खाती है तरह से प्रयोग विफल हो सकता है, और घटित होने वाली बुरी घटनाओं की अपेक्षित संख्या 1 से कम है।)
इस मामले में, विफलता की सशर्त संभावना को 1 से नीचे रखने के लिए, Q की सशर्त अपेक्षा को सीमा से नीचे (या ऊपर) रखना पर्याप्त है। ऐसा करने के लिए, विफलता की सशर्त संभावना की गणना करने के बजाय, एल्गोरिदम क्यू की सशर्त अपेक्षा की गणना करता है और तदनुसार आगे बढ़ता है: प्रत्येक आंतरिक नोड पर, कुछ बच्चे होते हैं जिनकी सशर्त अपेक्षा अधिकतम (कम से कम) नोड की सशर्त अपेक्षा होती है; एल्गोरिथ्म वर्तमान नोड से ऐसे बच्चे की ओर बढ़ता है, इस प्रकार सशर्त अपेक्षा को सीमा से नीचे (ऊपर) रखता है।
- 'निराशावादी अनुमानक का उपयोग करना:' कुछ मामलों में, मात्रा Q की सटीक सशर्त अपेक्षा के लिए प्रॉक्सी के रूप में, उचित रूप से तंग सीमा का उपयोग किया जाता है जिसे निराशावादी अनुमानक कहा जाता है। निराशावादी अनुमानक वर्तमान स्थिति का कार्य है। वर्तमान स्थिति को देखते हुए यह Q की सशर्त अपेक्षा के लिए ऊपरी (या निचला) होना चाहिए, और यह प्रयोग के प्रत्येक यादृच्छिक चरण के साथ अपेक्षा में गैर-बढ़ती (या गैर-घटती) होनी चाहिए। आमतौर पर, अच्छे निराशावादी अनुमानक की गणना मूल प्रमाण के तर्क को सटीक रूप से विखंडित करके की जा सकती है।
सशर्त अपेक्षाओं का उपयोग करने वाला उदाहरण
यह उदाहरण सशर्त अपेक्षा का उपयोग करके सशर्त संभावनाओं की विधि को प्रदर्शित करता है।
मैक्स-कट लेम्मा
किसी भी अप्रत्यक्ष ग्राफ़ (असतत गणित) जी = (वी, ई) को देखते हुए, अधिकतम कटौती समस्या ग्राफ़ के प्रत्येक शीर्ष को दो रंगों (जैसे काले या सफेद) में से के साथ रंगना है ताकि किनारों की संख्या को अधिकतम किया जा सके जिनके अंतिम बिंदु हैं अलग - अलग रंग। (कहो ऐसी धार कटी है।)
'मैक्स-कट लेम्मा:' किसी भी ग्राफ G = (V, E) में, कम से कम |E|/2 किनारों को काटा जा सकता है।
'संभाव्य प्रमाण।' गोरा सिक्का उछालकर प्रत्येक शीर्ष को काला या सफेद रंग दें। गणना के अनुसार, ई में किसी भी किनारे ई के लिए, इसके कटने की संभावना 1/2 है। इस प्रकार, अपेक्षित मान#रैखिकता के अनुसार, काटे गए किनारों की अपेक्षित संख्या |E|/2 है। इस प्रकार, ऐसा रंग मौजूद है जो कम से कम |E|/2 किनारों को काटता है। QED
सशर्त अपेक्षाओं के साथ सशर्त संभावनाओं की विधि
सशर्त संभावनाओं की विधि को लागू करने के लिए, पहले यादृच्छिक प्रयोग को छोटे यादृच्छिक चरणों के अनुक्रम के रूप में मॉडल करें। इस मामले में प्रत्येक चरण को किसी विशेष शीर्ष के लिए रंग की पसंद के रूप में मानना स्वाभाविक है (इसलिए |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. वी में प्रत्येक शीर्ष यू के लिए (किसी भी क्रम में): 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)अब तक जोड़े गए शीर्षों को दर्शाता है। चलो आर(टी)उन शीर्षों को दर्शाता है जिन पर अभी तक विचार नहीं किया गया है, और जिनका एस में कोई पड़ोसी नहीं है(टी). पहले t चरणों को देखते हुए, मूल प्रमाण में तर्क के बाद, R में कोई भी शीर्ष w दिया गया है(t) में S में जोड़े जाने की सशर्त संभावना कम से कम 1/(d(w)+1) है, इसलिए Q की सशर्त अपेक्षा कम से कम है
चलो Q(t)उपर्युक्त मात्रा को दर्शाता है, जिसे सशर्त अपेक्षा के लिए 'निराशावादी अनुमानक' कहा जाता है।
प्रमाण से पता चला कि निराशावादी अनुमानक शुरू में कम से कम |V|/(D+1) है। (अर्थात्, प्र(0) ≥ |V|/(D+1).) एल्गोरिदम निराशावादी अनुमानक को घटने से रोकने के लिए प्रत्येक विकल्प चुनेगा, अर्थात, ताकि Q(t+1) ≥ Q(टी)प्रत्येक टी के लिए। चूँकि निराशावादी अनुमानक सशर्त अपेक्षा पर निचली सीमा रखता है, यह सुनिश्चित करेगा कि सशर्त अपेक्षा |V|/(D+1) से ऊपर रहे, जो बदले में यह सुनिश्चित करेगा कि विफलता की सशर्त संभावना 1 से नीचे रहे।
मान लीजिए कि आप अगले ((t+1)-st) चरण में एल्गोरिथम द्वारा माना गया शीर्ष है।
यदि आपका पहले से ही S में कोई पड़ोसी है, तो आपको S में नहीं जोड़ा जाता है और (Q के निरीक्षण द्वारा)(t)), निराशावादी अनुमानक अपरिवर्तित है। यदि S में u का कोई पड़ोसी नहीं है, तो S में u जोड़ा जाता है।
गणना के अनुसार, यदि यू को शेष शीर्षों से यादृच्छिक रूप से चुना जाता है, तो निराशावादी अनुमानक में अपेक्षित वृद्धि गैर-नकारात्मक है। ['हिसाब।' आर में शीर्ष चुनने पर शर्त(टी), निराशावादी अनुमानक में दिए गए पद 1/(d(w)+1) को योग से हटा दिए जाने की संभावना अधिकतम (d(w)+1)/|R है(टी)|, इसलिए योग में प्रत्येक पद में अपेक्षित कमी अधिकतम 1/|आर है(टी)|. आर हैं(t)योग में शर्तें। इस प्रकार, योग में अपेक्षित कमी अधिकतम 1 है। इस बीच, S का आकार 1 बढ़ जाता है।]
इस प्रकार, आपके पास कुछ विकल्प मौजूद होने चाहिए जो निराशावादी अनुमानक को कम होने से रोकते हैं।
निराशावादी अनुमानक को अधिकतम करने वाला एल्गोरिदम
परिणामी निराशावादी अनुमानक को अधिकतम करने के लिए नीचे दिया गया एल्गोरिदम प्रत्येक शीर्ष यू को चुनता है। पिछले विचारों के अनुसार, यह निराशावादी अनुमानक को कम होने से रोकता है और सफल परिणाम की गारंटी देता है।
नीचे, एन(t)(u) R में आपके पड़ोसियों को दर्शाता है(t) (अर्थात्, आपके पड़ोसी जो न तो S में हैं और न ही उनका कोई पड़ोसी S में है)।
1. खाली सेट होने के लिए S को आरंभ करें।
2. जबकि एस में कोई पड़ोसी नहीं होने के कारण अभी तक नहीं माना जाने वाला शीर्ष यू मौजूद है:
3. S में ऐसा शीर्ष u जोड़ें जहां u न्यूनतम हो .
4. वापसी एस.
एल्गोरिदम जो निराशावादी अनुमानक को अधिकतम नहीं करते
सशर्त संभावनाओं की विधि के काम करने के लिए, यह पर्याप्त है यदि एल्गोरिदम निराशावादी अनुमानक को घटने (या बढ़ने, जैसा उपयुक्त हो) से रखता है। एल्गोरिदम को निराशावादी अनुमानक को अधिकतम (या न्यूनतम) करना आवश्यक नहीं है। यह एल्गोरिदम प्राप्त करने में कुछ लचीलापन देता है। अगले दो एल्गोरिदम इसे दर्शाते हैं।
1. खाली सेट होने के लिए S को आरंभ करें। 2. जबकि ग्राफ़ में शीर्ष u मौजूद है जिसका S में कोई पड़ोसी नहीं है: 3. S में ऐसा शीर्ष u जोड़ें, जहां u, d(u) (u की प्रारंभिक डिग्री) को न्यूनतम करता है। 4. वापसी एस.
1. खाली सेट होने के लिए S को आरंभ करें। 2. जबकि शेष ग्राफ खाली नहीं है: 3. S में शीर्ष u जोड़ें, जहां शेष ग्राफ़ में u की न्यूनतम डिग्री है। 4. ग्राफ़ से आप और उसके सभी पड़ोसियों को हटा दें। 5. वापसी एस.
प्रत्येक एल्गोरिदम का विश्लेषण पहले की तरह ही निराशावादी अनुमानक के साथ किया जाता है। किसी भी एल्गोरिदम के प्रत्येक चरण के साथ, निराशावादी अनुमानक में शुद्ध वृद्धि होती है
जहां एन(t)(u) शेष ग्राफ़ में (अर्थात R में) u के पड़ोसियों को दर्शाता है(टी)).
पहले एल्गोरिदम के लिए, शुद्ध वृद्धि गैर-नकारात्मक है क्योंकि, यू की पसंद से,
- ,
जहां d(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.
