मोंटे कार्लो एल्गोरिथ्म
 | This article includes a list of general references, but it lacks sufficient corresponding inline citations. (August 2011) (Learn how and when to remove this template message) |
कम्प्यूटिंग में, एक मोंटे कार्लो एल्गोरिथम एक यादृच्छिक एल्गोरिथम है जिसका आउटपुट एक निश्चित (आमतौर पर छोटी) संभावना के साथ गलत हो सकता है। इस तरह के एल्गोरिदम के दो उदाहरण हैं कार्गर का एल्गोरिथम | कार्गर-स्टीन एल्गोरिथम[1] और न्यूनतम फीडबैक आर्क सेट के लिए मोंटे कार्लो एल्गोरिदम।[2] नाम मोंटे कार्लो में मोनाको की रियासत में भव्य मोंटे कार्लो कैसीनो को संदर्भित करता है, जो दुनिया भर में जुए के प्रतीक के रूप में जाना जाता है। मोंटे कार्लो शब्द पहली बार 1947 में निकोलस मेट्रोपोलिस द्वारा पेश किया गया था।[3] लास वेगास एल्गोरिदम मोंटे कार्लो एल्गोरिदम का एक दोहरा (गणित) है जो कभी भी गलत उत्तर नहीं देता है। हालाँकि, वे अपने काम के हिस्से के रूप में यादृच्छिक विकल्प चुन सकते हैं। नतीजतन, लिया गया समय रन के बीच भिन्न हो सकता है, यहां तक कि एक ही इनपुट के साथ भी।
यदि मोंटे कार्लो एल्गोरिथ्म द्वारा दिया गया उत्तर सही है या नहीं, यह सत्यापित करने के लिए एक प्रक्रिया है, और एक सही उत्तर की संभावना शून्य से ऊपर है, तो प्रायिकता एक के साथ, उत्तरों का परीक्षण करते समय एल्गोरिदम को बार-बार चलाने से अंततः एक सही उत्तर मिलेगा . यह प्रक्रिया लास वेगास एल्गोरिथम है या नहीं यह इस बात पर निर्भर करता है कि क्या संभावना के साथ रुकने को परिभाषा को पूरा करने के लिए माना जाता है।
एक तरफा बनाम दो तरफा त्रुटि
जबकि नियतात्मक एल्गोरिथम द्वारा दिया गया उत्तर हमेशा सही होने की उम्मीद की जाती है, यह मोंटे कार्लो एल्गोरिदम के मामले में नहीं है। निर्णय समस्याओं के लिए, इन एल्गोरिदम को आम तौर पर या तो झूठे-पक्षपाती या सत्य-पक्षपाती के रूप में वर्गीकृत किया जाता है। एक झूठा-पक्षपाती मोंटे कार्लो एल्गोरिथम हमेशा सही होता है जब वह गलत रिटर्न देता है; एक सत्य-पक्षपाती एल्गोरिथम हमेशा सही होता है जब वह सत्य लौटाता है। जबकि यह एकतरफा त्रुटियों वाले एल्गोरिदम का वर्णन करता है, अन्य में कोई पूर्वाग्रह नहीं हो सकता है; कहा जाता है कि इनमें दो तरफा त्रुटियाँ होती हैं। वे जो उत्तर प्रदान करते हैं (या तो सही या गलत) कुछ बंधी हुई संभावना के साथ गलत या सही होगा।
उदाहरण के लिए, सोलोवे-स्ट्रैसन प्राइमलिटी टेस्ट का उपयोग यह निर्धारित करने के लिए किया जाता है कि दी गई संख्या एक अभाज्य संख्या है या नहीं। अभाज्य संख्या इनपुट के लिए यह हमेशा सही उत्तर देता है; समग्र इनपुट के लिए, यह कम से कम प्रायिकता के साथ गलत उत्तर देता है 1⁄2 और सत्य से कम संभावना के साथ 1⁄2. इस प्रकार, एल्गोरिथम से गलत उत्तर निश्चित रूप से सही होते हैं, जबकि सही उत्तर अनिश्चित रहते हैं; यह एक कहा जाता है1⁄2-गलत-पक्षपाती एल्गोरिथम सही करें।
प्रवर्धन
एकतरफा त्रुटियों वाले मोंटे कार्लो एल्गोरिथम के लिए, एल्गोरिथम k बार चलाकर विफलता की संभावना को कम किया जा सकता है (और सफलता की संभावना को बढ़ाया जा सकता है)। फिर से सोलोवे-स्ट्रैसन एल्गोरिथम पर विचार करें जो कि है1⁄2-गलत-पक्षपाती सही। यदि यह k पुनरावृत्तियों के भीतर 'गलत' प्रतिक्रिया तक पहुँचता है, और अन्यथा 'सही' लौटाता है, तो कोई भी इस एल्गोरिथ्म को कई बार 'गलत' उत्तर देकर चला सकता है। इस प्रकार, यदि संख्या अभाज्य है तो उत्तर हमेशा सही होता है, और यदि संख्या संयुक्त है तो उत्तर कम से कम 1−(1−) की प्रायिकता के साथ सही होता है।1⁄2)के</सुप> = 1−2-क</सुप>.
मोंटे कार्लो निर्णय एल्गोरिदम के लिए दो तरफा त्रुटि के साथ, विफलता की संभावना फिर से कम हो सकती है एल्गोरिथ्म k बार चल रहा है और उत्तरों के बहुमत समारोह को वापस कर रहा है।
जटिलता वर्ग
जटिलता वर्ग बाउंडेड-त्रुटि संभाव्य बहुपद उन निर्णय समस्याओं का वर्णन करता है जिन्हें दो तरफा त्रुटियों की बाध्य संभावना के साथ बहुपद-समय मोंटे कार्लो एल्गोरिदम द्वारा हल किया जा सकता है, और जटिलता वर्ग आरपी (जटिलता) उन समस्याओं का वर्णन करता है जिन्हें मोंटे कार्लो द्वारा हल किया जा सकता है एकतरफा त्रुटि की सीमित संभावना के साथ एल्गोरिदम: यदि सही उत्तर गलत है, तो एल्गोरिदम हमेशा ऐसा कहता है, लेकिन यह कुछ उदाहरणों के लिए गलत उत्तर दे सकता है जहां सही उत्तर सत्य है। इसके विपरीत, जटिलता वर्ग ZPP (जटिलता) बहुपद अपेक्षित समय लास वेगास एल्गोरिदम द्वारा हल की जाने वाली समस्याओं का वर्णन करता है। ZPP ⊆ RP ⊆ BPP, लेकिन यह ज्ञात नहीं है कि इनमें से कोई जटिलता वर्ग एक दूसरे से अलग है या नहीं; अर्थात्, मोंटे कार्लो एल्गोरिदम में लास वेगास एल्गोरिदम की तुलना में अधिक कम्प्यूटेशनल शक्ति हो सकती है, लेकिन यह सिद्ध नहीं हुआ है। एक अन्य जटिलता वर्ग, पीपी (जटिलता), एक बहुपद-समय मोंटे कार्लो एल्गोरिथम के साथ निर्णय समस्याओं का वर्णन करता है जो एक सिक्के को फ़्लिप करने से अधिक सटीक है, लेकिन जहां त्रुटि की संभावना आवश्यक रूप से दूर नहीं हो सकती है 1⁄2.
कम्प्यूटेशनल संख्या सिद्धांत में अनुप्रयोग
जाने-माने मोंटे कार्लो एल्गोरिदम में सोलोवे-स्ट्रैसन प्राइमलिटी टेस्ट, बैली-पीएसडब्ल्यू प्राइमलिटी टेस्ट, मिलर-राबिन प्राइमलिटी टेस्ट और कम्प्यूटेशनल समूह सिद्धांत में श्रेयर-सिम्स एल्गोरिथम के कुछ फास्ट वेरिएंट शामिल हैं।
यह भी देखें
- मोंटे कार्लो विधियाँ, यादृच्छिक नमूने लेने के आधार पर भौतिक सिमुलेशन और कम्प्यूटेशनल सांख्यिकी में उपयोग किए जाने वाले एल्गोरिदम
- अटलांटिक सिटी एल्गोरिदम
- लास वेगास एल्गोरिथम
संदर्भ
उद्धरण
- ↑ Karger, David R.; Stein, Clifford (July 1996). "A New Approach to the Minimum Cut Problem". J. ACM. 43 (4): 601–640. doi:10.1145/234533.234534. ISSN 0004-5411. S2CID 5385337.
- ↑ Kudelić, Robert (2016-04-01). "Monte-Carlo randomized algorithm for minimal feedback arc set problem". Applied Soft Computing. 41: 235–246. doi:10.1016/j.asoc.2015.12.018.
- ↑ Metropolis, N. (1987). "The beginning of the Monte Carlo method" (PDF). Los Alamos Science (1987 Special Issue dedicated to Stanislaw Ulam): 125–130.
स्रोत
- Motwani, Rajeev; Raghavan, Prabhakar (1995). यादृच्छिक एल्गोरिदम. New York: Cambridge University Press. ISBN 0-521-47465-5.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Ch 5. Probabilistic Analysis and Randomized Algorithms". एल्गोरिदम का परिचय (2nd ed.). Boston: MIT Press and McGraw-Hill. ISBN 0-262-53196-8.
- Berman, Kenneth A.; Paul, Jerome L. (2005). "Ch 24. Probabilistic and Randomized Algorithms". एल्गोरिदम: अनुक्रमिक, समानांतर और वितरित. Boston: Course Technology. ISBN 0-534-42057-5.
श्रेणी:यादृच्छिक एल्गोरिदम