लास वेगास एल्गोरिथ्म: Difference between revisions

From Vigyanwiki
(Created page with "कम्प्यूटिंग में, लास वेगास एल्गोरिदम एक यादृच्छिक एल्गोरिदम ह...")
 
No edit summary
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[ कम्प्यूटिंग ]] में, लास वेगास एल्गोरिदम एक [[यादृच्छिक एल्गोरिदम]] है जो हमेशा [[शुद्धता (कंप्यूटर विज्ञान)]] परिणाम देता है; अर्थात् यह सदैव सही परिणाम देता है अथवा असफलता की सूचना देता है। हालाँकि, लास वेगास एल्गोरिदम का रनटाइम इनपुट के आधार पर भिन्न होता है। लास वेगास एल्गोरिदम की सामान्य परिभाषा में यह प्रतिबंध शामिल है कि ''अपेक्षित'' रनटाइम सीमित होना चाहिए, जहां एल्गोरिदम में उपयोग की जाने वाली यादृच्छिक जानकारी, या एन्ट्रॉपी के स्थान पर किया जाता है। एक वैकल्पिक परिभाषा के लिए आवश्यक है कि लास वेगास एल्गोरिदम हमेशा समाप्त हो (प्रभावी विधि है), लेकिन समाधान खोजने में विफलता को इंगित करने के लिए एक आंशिक फ़ंक्शन#बॉटम तत्व आउटपुट कर सकता है।<ref name="Galbraith201222">{{cite book|title=सार्वजनिक कुंजी क्रिप्टोग्राफी का गणित|author=Steven D. Galbraith|publisher=Cambridge University Press|year=2012|isbn=978-1-107-01392-6|page=16}}</ref> लास वेगास एल्गोरिदम की प्रकृति उन्हें उन स्थितियों में उपयुक्त बनाती है जहां संभावित समाधानों की संख्या सीमित है, और जहां किसी उम्मीदवार समाधान की शुद्धता की पुष्टि करना अपेक्षाकृत आसान है जबकि समाधान ढूंढना जटिल है।
[[ कम्प्यूटिंग | कम्प्यूटिंग]] में, '''लास वेगास एल्गोरिथ्म''' एक [[यादृच्छिक एल्गोरिदम|यादृच्छिक एल्गोरिथ्म]] है जो हमेशा यथार्थ परिणाम देता है; अर्थात् यह सदैव सही परिणाम देता है अथवा असफलता की सूचना देता है। हालाँकि, लास वेगास एल्गोरिथ्म का कार्यावधि निविष्ट के आधार पर भिन्न होता है। लास वेगास एल्गोरिथ्म की सामान्य परिभाषा में यह प्रतिबंध सम्मिलित है कि अपेक्षित कार्यावधि सीमित होना चाहिए, जहां एल्गोरिथ्म में उपयोग की जाने वाली यादृच्छिक जानकारी, या एन्ट्रॉपी के स्थान पर किया जाता है। एक वैकल्पिक परिभाषा के लिए आवश्यक है कि लास वेगास एल्गोरिथ्म हमेशा समाप्त हो (प्रभावी विधि है), लेकिन समाधान खोजने में विफलता को इंगित करने के लिए एक आंशिक फलन प्रक्षेपण कर सकता है। <ref name="Galbraith201222">{{cite book|title=सार्वजनिक कुंजी क्रिप्टोग्राफी का गणित|author=Steven D. Galbraith|publisher=Cambridge University Press|year=2012|isbn=978-1-107-01392-6|page=16}}</ref> लास वेगास एल्गोरिथ्म की प्रकृति उन्हें उन स्थितियों में उपयुक्त बनाती है जहां संभावित समाधानों की संख्या सीमित है, और जहां किसी पदान्वेषी समाधान की शुद्धता की पुष्टि करना अपेक्षाकृत आसान है जबकि समाधान ढूंढना जटिल है।


लास वेगास एल्गोरिदम कृत्रिम बुद्धिमत्ता के क्षेत्र में और कंप्यूटर विज्ञान और संचालन अनुसंधान के अन्य क्षेत्रों में प्रमुख हैं। एआई में, [[स्टोकेस्टिक स्थानीय खोज]] (एसएलएस) एल्गोरिदम को लास वेगास प्रकार का माना जाता है{{Citation needed|date=February 2021}}. एसएलएस एल्गोरिदम का उपयोग एनपी-पूर्णता | एनपी-पूर्ण निर्णय समस्याओं और [[एनपी-कठोरता]] | एनपी-हार्ड कॉम्बिनेटरियल अनुकूलन समस्याओं को संबोधित करने के लिए किया गया है।<ref>Selman, B., Kautz, H. A., & Cohen, B. “Local search strategies for satisfiability testing.” (1996).</ref> हालाँकि, कुछ व्यवस्थित खोज विधियाँ, जैसे प्रस्तावात्मक संतुष्टि (SAT) के लिए डेविस-पुटनम एल्गोरिदम के आधुनिक संस्करण, गैर-नियतात्मक निर्णयों का भी उपयोग करते हैं, और इस प्रकार उन्हें लास वेगास एल्गोरिदम भी माना जा सकता है।<ref>Hoos, Holger H.. “On the Empirical Evaluation of Las Vegas Algorithms — Position Paper.” (1998).</ref>
लास वेगास एल्गोरिथ्म कृत्रिम बुद्धिमत्ता के क्षेत्र में और कंप्यूटर विज्ञान और संचालन अनुसंधान के अन्य क्षेत्रों में प्रमुख हैं। एआई में, [[स्टोकेस्टिक स्थानीय खोज]] (एसएलएस) एल्गोरिथ्म को लास वेगास प्रकार का माना जाता है। एसएलएस एल्गोरिथ्म का उपयोग एनपी-पूर्णता निर्णय समस्याओं और एनपी-कठोर संयुक्त अनुकूलन समस्याओं को संबोधित करने के लिए किया गया है। <ref>Selman, B., Kautz, H. A., & Cohen, B. “Local search strategies for satisfiability testing.” (1996).</ref> हालाँकि, कुछ व्यवस्थित खोज विधियाँ, जैसे प्रस्तावात्मक संतुष्टि (एसएटी) के लिए डेविस-पुटनम एल्गोरिथ्म के आधुनिक संस्करण, गैर-नियतात्मक निर्णयों का भी उपयोग करते हैं, और इस प्रकार उन्हें लास वेगास एल्गोरिथ्म भी माना जा सकता है। <ref>Hoos, Holger H.. “On the Empirical Evaluation of Las Vegas Algorithms — Position Paper.” (1998).</ref>




== इतिहास ==
== इतिहास ==
लास वेगास एल्गोरिदम को 1979 में लास्ज़लो बाबई द्वारा [[ग्राफ समरूपता समस्या]] के संदर्भ में, [[मोंटे कार्लो एल्गोरिथ्म]] के दोहरे के रूप में पेश किया गया था।<ref>* [[László Babai]], [http://people.cs.uchicago.edu/~laci/lasvegas79.pdf Monte-Carlo algorithms in graph isomorphism testing], Université de Montréal, D.M.S. No. 79-10.
लास वेगास एल्गोरिथ्म को 1979 में लास्ज़लो बाबई द्वारा [[ग्राफ समरूपता समस्या|आलेख समरूपता समस्या]] के संदर्भ में, [[मोंटे कार्लो एल्गोरिथ्म]] के दोहरे के रूप में प्रस्तुत किया गया था। <ref>* [[László Babai]], [http://people.cs.uchicago.edu/~laci/lasvegas79.pdf Monte-Carlo algorithms in graph isomorphism testing], Université de Montréal, D.M.S. No. 79-10.
* [[Leonid Levin]], [[arxiv:cs.CR/0012023|The Tale of One-way Functions]], ''Problems of Information Transmission'', vol. 39 (2003), 92-103.
* [[Leonid Levin]], [[arxiv:cs.CR/0012023|The Tale of One-way Functions]], ''Problems of Information Transmission'', vol. 39 (2003), 92-103.
* Dan Grundy, [http://www.cs.kent.ac.uk/people/staff/eab2/crypto/thesis.web.pdf Concepts and Calculation in Cryptography] {{Webarchive|url=https://web.archive.org/web/20160412010348/https://www.cs.kent.ac.uk/people/staff/eab2/crypto/thesis.web.pdf |date=2016-04-12 }}, University of Kent, Ph.D. thesis, 2008</ref> पिता<ref>Babai, László. “Monte-Carlo algorithms in graph isomorphism testing.” (1979).</ref> सिक्का उछालने से जुड़े एक उदाहरण के साथ लास वेगास एल्गोरिदम शब्द पेश किया गया: एल्गोरिदम स्वतंत्र सिक्का उछाल की एक श्रृंखला पर निर्भर करता है, और विफलता की एक छोटी संभावना है (कोई परिणाम नहीं)। हालाँकि, मोंटे कार्लो एल्गोरिदम के विपरीत, लास वेगास एल्गोरिदम किसी भी रिपोर्ट किए गए परिणाम की शुद्धता की गारंटी दे सकता है।
* Dan Grundy, [http://www.cs.kent.ac.uk/people/staff/eab2/crypto/thesis.web.pdf Concepts and Calculation in Cryptography] {{Webarchive|url=https://web.archive.org/web/20160412010348/https://www.cs.kent.ac.uk/people/staff/eab2/crypto/thesis.web.pdf |date=2016-04-12 }}, University of Kent, Ph.D. thesis, 2008</ref> बाबई <ref>Babai, László. “Monte-Carlo algorithms in graph isomorphism testing.” (1979).</ref> सिक्का उछालने से जुड़े एक उदाहरण के साथ लास वेगास एल्गोरिथ्म शब्द प्रस्तुत किया गया: एल्गोरिथ्म स्वतंत्र सिक्का उछाल की एक श्रृंखला पर निर्भर करता है, और विफलता की एक छोटी संभावना है (कोई परिणाम नहीं)। हालाँकि, मोंटे कार्लो एल्गोरिथ्म के विपरीत, लास वेगास एल्गोरिथ्म किसी भी प्रतिवेदन किए गए परिणाम की शुद्धता की प्रत्याभुति दे सकता है।


== उदाहरण ==
== उदाहरण ==
<सिंटैक्सहाइलाइट लैंग= जावा लाइन= 1 >
// Las Vegas algorithm
// लास वेगास एल्गोरिदम
repeat:
दोहराना:
    k = RandInt(n)
    के = रैंडइंट (एन)
    if A[k] == 1,
    यदि ए[के] == 1,
        return k;
        वापसी क;
जैसा कि ऊपर बताया गया है, लास वेगास एल्गोरिथ्म हमेशा सही परिणाम लौटाते हैं। उपरोक्त कूट इस संपत्ति को दर्शाता है। एक चर k यादृच्छिक रूप से उत्पन्न होता है; k उत्पन्न होने के बाद, k का उपयोग सरणी A को अनुक्रमित करने के लिए किया जाता है। यदि इस सूचकांक में मान 1 है, तो k वापस कर दिया जाता है; अन्यथा, एल्गोरिथ्म इस प्रक्रिया को तब तक दोहराता है जब तक कि उसे 1 नहीं मिल जाता। हालांकि यह लास वेगास एल्गोरिथ्म सही उत्तर खोजने की प्रत्याभुति देता है, लेकिन इसका कोई निश्चित कार्यावधि नहीं है; यादृच्छिकीकरण (उपरोक्त कूट की पंक्ति 3 में) के कारण, एल्गोरिथ्म समाप्त होने से पहले स्वेच्छाचारी ढंग से बहुत अधिक समय व्यतीत करना संभव है।
</सिंटैक्सहाइलाइट>
 
जैसा कि ऊपर बताया गया है, लास वेगास एल्गोरिदम हमेशा सही परिणाम लौटाते हैं। उपरोक्त कोड इस संपत्ति को दर्शाता है। एक चर k यादृच्छिक रूप से उत्पन्न होता है; k उत्पन्न होने के बाद, k का उपयोग सरणी A को अनुक्रमित करने के लिए किया जाता है। यदि इस सूचकांक में मान 1 है, तो k वापस कर दिया जाता है; अन्यथा, एल्गोरिथम इस प्रक्रिया को तब तक दोहराता है जब तक कि उसे 1 नहीं मिल जाता। हालांकि यह लास वेगास एल्गोरिथम सही उत्तर खोजने की गारंटी देता है, लेकिन इसका कोई निश्चित रनटाइम नहीं है; रैंडमाइजेशन (उपरोक्त कोड की पंक्ति 3 में) के कारण, एल्गोरिदम समाप्त होने से पहले मनमाने ढंग से बहुत अधिक समय व्यतीत करना संभव है।


== परिभाषा ==
== परिभाषा ==
यह अनुभाग वे स्थितियाँ प्रदान करता है जो किसी एल्गोरिथम के लास वेगास प्रकार के होने की विशेषता बताती हैं।
यह अनुभाग वे स्थितियाँ प्रदान करता है जो किसी एल्गोरिथ्म के लास वेगास प्रकार के होने की विशेषता बताती हैं।


एक एल्गोरिथम ए, समस्या वर्ग X के लिए एक लास वेगास एल्गोरिथम है, यदि<ref>H.H. Hoos and T. Stützle. Evaluating Las Vegas Algorithms — Pitfalls and Remedies. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI-98), pages 238–245. Morgan Kaufmann Publishers, San Francisco, CA, 1998.</ref>
एक एल्गोरिथ्म A, समस्या वर्ग X के लिए एक लास वेगास एल्गोरिथ्म है, यदि <ref>H.H. Hoos and T. Stützle. Evaluating Las Vegas Algorithms — Pitfalls and Remedies. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI-98), pages 238–245. Morgan Kaufmann Publishers, San Francisco, CA, 1998.</ref>
#जब भी किसी दिए गए समस्या उदाहरण x∈X के लिए यह एक समाधान s लौटाता है, तो s को x का वैध समाधान होने की गारंटी दी जाती है
#जब भी किसी दिए गए समस्या उदाहरण x∈X के लिए यह एक समाधान s लौटाता है, तो s को x का वैध समाधान होने की प्रत्याभुति दी जाती है।
#प्रत्येक दिए गए उदाहरण x पर, A का रन-टाइम एक यादृच्छिक चर RT है<sub>A,x</sub>
#प्रत्येक दिए गए उदाहरण x पर, A का रन-टाइम एक यादृच्छिक चर RT<sub>A,x</sub> है।
लास वेगास एल्गोरिदम के लिए पूर्णता की तीन धारणाएँ हैं:
लास वेगास एल्गोरिथ्म के लिए पूर्णता की तीन धारणाएँ हैं:


* पूर्ण लास वेगास एल्गोरिदम को रन-टाइम टी के भीतर प्रत्येक हल करने योग्य समस्या को हल करने की गारंटी दी जा सकती है<small>max,</small> जहां टी<small>max</small> एक उदाहरण-निर्भर स्थिरांक है।
* पूर्ण लास वेगास एल्गोरिथ्म को रन-टाइम T<small>max</small> के भीतर प्रत्येक हल करने योग्य समस्या को हल करने की प्रत्याभुति दी जा सकती है<small>,</small> जहां T<small>max</small> एक उदाहरण-निर्भर स्थिरांक है।


चलो पी(आरटी<sub>A,x</sub> ≤ टी) इस संभावना को निरूपित करें कि ए घुलनशील उदाहरण एक्स के लिए टी के भीतर समय में एक समाधान ढूंढ लेता है, तो ए बिल्कुल पूर्ण है यदि प्रत्येक एक्स के लिए मौजूद है
मान लीजिये P(RT<sub>A,x</sub> ≤ t) इस संभावना को निरूपित करें कि A घुलनशील उदाहरण X के लिए T के भीतर समय में एक समाधान ढूंढ लेता है, तो A बिल्कुल पूर्ण है यदि प्रत्येक X के लिए उपस्थित है


कुछ टी<small>max</small> ऐसा कि P(RT<sub>A,x</sub> ≤ टी<sub>max</sub>) = 1.
कुछ t<small>max</small> इस प्रकार कि P(RT<sub>A,x</sub> ≤ t<sub>max</sub>) = 1 है।


* लगभग पूर्ण लास वेगास एल्गोरिदम प्रत्येक समस्या को 1 में परिवर्तित होने वाली संभावना के साथ हल करते हैं क्योंकि रन-टाइम अनंत तक पहुंचता है। इस प्रकार, A लगभग पूर्ण है, यदि प्रत्येक उदाहरण x के लिए, lim<sub>t→∞</sub> पी(आरटी<sub>A,x</sub> ≤ टी) = 1.
* लगभग पूर्ण लास वेगास एल्गोरिथ्म प्रत्येक समस्या को 1 में परिवर्तित होने वाली संभावना के साथ हल करते हैं क्योंकि रन-टाइम अनंत तक पहुंचता है। इस प्रकार, A लगभग पूर्ण है, यदि प्रत्येक उदाहरण x के लिए, lim<sub>t→∞</sub> P(RT<sub>A,x</sub> ≤ t) = 1।
* अनिवार्य रूप से अपूर्ण लास वेगास एल्गोरिदम लास वेगास एल्गोरिदम हैं जो लगभग पूर्ण नहीं हैं।
* अनिवार्य रूप से अपूर्ण लास वेगास एल्गोरिथ्म लास वेगास एल्गोरिथ्म हैं जो लगभग पूर्ण नहीं हैं।


अनुमानित पूर्णता मुख्य रूप से सैद्धांतिक रुचि का विषय है, क्योंकि समाधान खोजने की समय सीमा आमतौर पर व्यावहारिक उपयोग के लिए बहुत बड़ी होती है।
अनुमानित पूर्णता मुख्य रूप से सैद्धांतिक रुचि का विषय है, क्योंकि समाधान खोजने की समय सीमा सामान्यतः व्यावहारिक उपयोग के लिए बहुत बड़ी होती है।


=== अनुप्रयोग परिदृश्य ===
=== अनुप्रयोग परिदृश्य ===
लास वेगास एल्गोरिदम में समस्या सेटिंग के आधार पर मूल्यांकन के लिए अलग-अलग मानदंड हैं। इन मानदंडों को अलग-अलग समय सीमाओं के साथ तीन श्रेणियों में विभाजित किया गया है क्योंकि लास वेगास एल्गोरिदम में निर्धारित समय जटिलता नहीं है। यहां कुछ संभावित अनुप्रयोग परिदृश्य दिए गए हैं:
लास वेगास एल्गोरिथ्म में समस्या समायोजन के आधार पर मूल्यांकन के लिए अलग-अलग मानदंड हैं। इन मानदंडों को अलग-अलग समय सीमाओं के साथ तीन श्रेणियों में विभाजित किया गया है क्योंकि लास वेगास एल्गोरिथ्म में निर्धारित समय जटिलता नहीं है। यहां कुछ संभावित अनुप्रयोग परिदृश्य दिए गए हैं:


*प्रकार 1: कोई समय सीमा नहीं है, जिसका अर्थ है कि एल्गोरिदम तब तक चलता है जब तक उसे समाधान नहीं मिल जाता।
*प्रकार 1: कोई समय सीमा नहीं है, जिसका अर्थ है कि एल्गोरिथ्म तब तक चलता है जब तक उसे समाधान नहीं मिल जाता।
*प्रकार 2: एक समय सीमा है<sub>max</sub> परिणाम जानने के लिए.
*प्रकार 2: परिणाम जानने के लिए एक समय सीमा t<sub>max</sub> है।
*प्रकार 3: किसी समाधान की उपयोगिता समाधान खोजने में लगने वाले समय से निर्धारित होती है।
*प्रकार 3: किसी समाधान की उपयोगिता समाधान खोजने में लगने वाले समय से निर्धारित होती है।


(टाइप 1 और टाइप 2 टाइप 3 के विशेष मामले हैं।)
(टाइप 1 और टाइप 2 टाइप 3 के विशेष स्तिथि हैं।)


टाइप 1 के लिए जहां कोई समय सीमा नहीं है, औसत रन-टाइम रन-टाइम व्यवहार का प्रतिनिधित्व कर सकता है। यह टाइप 2 के लिए समान मामला नहीं है।
टाइप 1 के लिए जहां कोई समय सीमा नहीं है, औसत रन-टाइम रन-टाइम व्यवहार का प्रतिनिधित्व कर सकता है। यह टाइप 2 के लिए समान मामला नहीं है।
Line 52: Line 49:
यहाँ, P(RT ≤ t<sub>max</sub>), जो समय के भीतर समाधान खोजने की संभावना है, इसके रन-टाइम व्यवहार का वर्णन करता है।
यहाँ, P(RT ≤ t<sub>max</sub>), जो समय के भीतर समाधान खोजने की संभावना है, इसके रन-टाइम व्यवहार का वर्णन करता है।


टाइप 3 के मामले में, इसके रन-टाइम व्यवहार को केवल रन-टाइम डिस्ट्रीब्यूशन फ़ंक्शन rtd द्वारा दर्शाया जा सकता है: R → [0,1] जिसे rtd(t) = P(RT ≤ t) या इसके सन्निकटन के रूप में परिभाषित किया गया है।
टाइप 3 कि स्तिथि में, इसके रन-टाइम व्यवहार को केवल रन-टाइम वियोजन फलन rtd द्वारा दर्शाया जा सकता है: R → [0,1] जिसे rtd(t) = P(RT ≤ t) या इसके सन्निकटन के रूप में परिभाषित किया गया है।


रन-टाइम डिस्ट्रीब्यूशन (आरटीडी) लास वेगास एल्गोरिदम के रन-टाइम व्यवहार का वर्णन करने का विशिष्ट तरीका है।
रन-टाइम वियोजन (आरटीडी) लास वेगास एल्गोरिथ्म के रन-टाइम व्यवहार का वर्णन करने का विशिष्ट तरीका है।


इस डेटा के साथ, हम आसानी से अन्य मानदंड प्राप्त कर सकते हैं जैसे कि औसत रन-टाइम, मानक विचलन, माध्यिका, प्रतिशत, या मनमानी समय-सीमा टी के लिए सफलता संभावनाएं पी (आरटी ≤ टी)।
इस डेटा के साथ, हम आसानी से अन्य मानदंड प्राप्त कर सकते हैं जैसे कि औसत रन-टाइम, मानक विचलन, माध्यिका, प्रतिशत, या स्वेच्छाचारी समय-सीमा T के लिए सफलता संभावनाएं ''P''(''RT'' ≤ ''t'') है।


== अनुप्रयोग ==
== अनुप्रयोग ==


=== सादृश्य ===
=== सादृश्य ===
लास वेगास एल्गोरिदम [[खोज समस्या]]ओं में अक्सर सामने आते हैं। उदाहरण के लिए, कोई व्यक्ति ऑनलाइन कुछ जानकारी खोज रहा है तो वह वांछित जानकारी के लिए संबंधित वेबसाइटों पर खोज कर सकता है। इस प्रकार समय की जटिलता भाग्यशाली होने और सामग्री को तुरंत ढूंढने से लेकर, दुर्भाग्यशाली होने और बड़ी मात्रा में समय खर्च करने तक होती है। एक बार सही वेबसाइट मिल जाए तो गलती की कोई संभावना नहीं रहती.<ref>Randomized Algorithms. ''Brilliant.org''. Retrieved 23:54, October 24, 2018, from https://brilliant.org/wiki/randomized-algorithms-overview/</ref>
लास वेगास एल्गोरिथ्म [[खोज समस्या]]ओं में प्रायः सामने आते हैं। उदाहरण के लिए, कोई व्यक्ति ऑनलाइन कुछ जानकारी खोज रहा है तो वह वांछित जानकारी के लिए संबंधित वेबसाइटों पर खोज कर सकता है। इस प्रकार समय की जटिलता भाग्यशाली होने और सामग्री को तुरंत ढूंढने से लेकर, दुर्भाग्यशाली होने और बड़ी मात्रा में समय खर्च करने तक होती है। एक बार सही वेबसाइट मिल जाए तो गलती की कोई संभावना नहीं रहती। <ref>Randomized Algorithms. ''Brilliant.org''. Retrieved 23:54, October 24, 2018, from https://brilliant.org/wiki/randomized-algorithms-overview/</ref>




Line 78: Line 75:
     Combine the responses in order to obtain a sorted array."""
     Combine the responses in order to obtain a sorted array."""
</syntaxhighlight>
</syntaxhighlight>
एक सरल उदाहरण यादृच्छिक क्विकॉर्ट है, जहां धुरी को यादृच्छिक रूप से चुना जाता है, और तत्वों को तीन विभाजनों में विभाजित करता है: धुरी से कम तत्व, धुरी के बराबर तत्व, और धुरी से बड़े तत्व। यादृच्छिक [[जल्दी से सुलझाएं]] के लिए बहुत सारे संसाधनों की आवश्यकता होती है लेकिन आउटपुट के रूप में हमेशा क्रमबद्ध सरणी उत्पन्न होती है।<ref>{{Cite news |url = https://towardsdatascience.com/from-las-vegas-to-monte-carlo-randomized-algorithms-in-machine-learning-systems-5ac29e2909de |title = From Las Vegas to Monte Carlo: Randomized Algorithms in Machine Learning Systems |date=2018-09-07 |work=Towards Data Science |access-date=2018-10-25 }}</ref>
एक सरल उदाहरण यादृच्छिक क्विकॉर्ट है, जहां धुरी को यादृच्छिक रूप से चुना जाता है, और तत्वों को तीन विभाजनों में विभाजित करता है: धुरी से कम तत्व, धुरी के बराबर तत्व, और धुरी से बड़े तत्व हैं। [[जल्दी से सुलझाएं|यादृच्छिक क्विकॉर्ट]] के लिए बहुत सारे संसाधनों की आवश्यकता होती है लेकिन प्रक्षेपण के रूप में हमेशा क्रमबद्ध सरणी उत्पन्न होती है। <ref>{{Cite news |url = https://towardsdatascience.com/from-las-vegas-to-monte-carlo-randomized-algorithms-in-machine-learning-systems-5ac29e2909de |title = From Las Vegas to Monte Carlo: Randomized Algorithms in Machine Learning Systems |date=2018-09-07 |work=Towards Data Science |access-date=2018-10-25 }}</ref> यह स्पष्ट है कि क्विकसॉर्ट हमेशा समाधान उत्पन्न करता है, जो इस स्तिथि में क्रमबद्ध सरणी है। दुर्भाग्य से, समय की जटिलता उतनी स्पष्ट नहीं है। यह पता चला है कि कार्यावधि इस बात पर निर्भर करता है कि हम किस तत्व को धुरी के रूप में चुनते हैं।
यह स्पष्ट है कि क्विकसॉर्ट हमेशा समाधान उत्पन्न करता है, जो इस मामले में क्रमबद्ध सरणी है। दुर्भाग्य से, समय की जटिलता उतनी स्पष्ट नहीं है। यह पता चला है कि रनटाइम इस बात पर निर्भर करता है कि हम किस तत्व को धुरी के रूप में चुनते हैं।


* सबसे ख़राब स्थिति Θ(n<sup>2</sup>) जब धुरी सबसे छोटा या सबसे बड़ा तत्व हो।
* सबसे ख़राब स्थिति Θ(n<sup>2</sup>) जब धुरी सबसे छोटा या सबसे बड़ा तत्व हो।
Line 89: Line 85:




* हालाँकि, रैंडमाइजेशन के माध्यम से, जहां धुरी को यादृच्छिक रूप से चुना जाता है और हर बार बिल्कुल मध्य मान होता है, क्विकसॉर्ट Θ(nlogn) में किया जा सकता है।
* हालाँकि, यादृच्छिकीकरण के माध्यम से, जहां धुरी को यादृच्छिक रूप से चुना जाता है और हर बार बिल्कुल मध्य मान होता है, क्विकसॉर्ट Θ(nlogn) में किया जा सकता है।


:<math>T(n) \leq 2*T(n/2) + \Theta(n)</math>
:<math>T(n) \leq 2*T(n/2) + \Theta(n)</math>
:<math>T(n) = \Theta(n\log(n))</math>
:<math>T(n) = \Theta(n\log(n))</math>
क्विकसॉर्ट का रनटाइम काफी हद तक इस बात पर निर्भर करता है कि धुरी का चयन कितनी अच्छी तरह किया गया है। यदि धुरी का मान या तो बहुत बड़ा या छोटा है, तो विभाजन असंतुलित हो जाएगा, जिसके परिणामस्वरूप खराब रनटाइम दक्षता होगी। हालाँकि, यदि धुरी का मान सरणी के मध्य के करीब है, तो विभाजन यथोचित रूप से संतुलित होगा, जिससे तेज़ रनटाइम प्राप्त होगा। चूंकि धुरी को बेतरतीब ढंग से चुना गया है, इसलिए चलने का समय ज्यादातर समय अच्छा और कभी-कभी खराब होगा।
क्विकसॉर्ट का कार्यावधि काफी हद तक इस बात पर निर्भर करता है कि धुरी का चयन कितनी अच्छी तरह किया गया है। यदि धुरी का मान या तो बहुत बड़ा या छोटा है, तो विभाजन असंतुलित हो जाएगा, जिसके परिणामस्वरूप खराब कार्यावधि दक्षता होगी। हालाँकि, यदि धुरी का मान सरणी के मध्य के करीब है, तो विभाजन यथोचित रूप से संतुलित होगा, जिससे तीव्र कार्यावधि प्राप्त होती है। चूंकि धुरी को बेतरतीब ढंग से चुना गया है, इसलिए चलने का समय ज्यादातर समय अच्छा और कभी-कभी खराब होगा।


औसत मामले में, यह निर्धारित करना कठिन है क्योंकि विश्लेषण इनपुट वितरण पर नहीं बल्कि एल्गोरिदम द्वारा किए गए यादृच्छिक विकल्पों पर निर्भर करता है। क्विकसॉर्ट के औसत की गणना उन सभी संभावित यादृच्छिक विकल्पों पर की जाती है जो एल्गोरिदम धुरी चुनते समय बना सकता है।
औसत स्तिथि में, यह निर्धारित करना कठिन है क्योंकि विश्लेषण निविष्ट वितरण पर नहीं बल्कि एल्गोरिथ्म द्वारा किए गए यादृच्छिक विकल्पों पर निर्भर करता है। क्विकसॉर्ट के औसत की गणना उन सभी संभावित यादृच्छिक विकल्पों पर की जाती है जो एल्गोरिथ्म धुरी चुनते समय बना सकता है।


हालाँकि सबसे खराब स्थिति वाला रनटाइम Θ(n) है<sup>2</sup>), औसत-केस रनटाइम Θ(nlogn) है। यह पता चला है कि सबसे खराब स्थिति अक्सर नहीं होती है। n के बड़े मानों के लिए, रनटाइम उच्च संभावना के साथ Θ(nlogn) है।
हालाँकि सबसे खराब स्थिति वाला कार्यावधि Θ(n)<sup>2</sup> है, औसत-केस कार्यावधि Θ(nlogn) है। यह पता चला है कि सबसे खराब स्थिति प्रायः नहीं होती है। n के बड़े मानों के लिए, कार्यावधि उच्च संभावना के साथ Θ(nlogn) है।


ध्यान दें कि हर बार धुरी के मध्य मान तत्व होने की संभावना n संख्याओं में से एक है, जो बहुत दुर्लभ है। हालाँकि, यह अभी भी वही रनटाइम है जब विभाजन 50% -50% के बजाय 10% -90% है क्योंकि रिकर्सन ट्री की गहराई अभी भी ओ (लॉगएन) होगी जिसमें रिकर्सन के प्रत्येक स्तर पर ओ (एन) समय लिया जाएगा। .
ध्यान दें कि हर बार धुरी के मध्य मान तत्व होने की संभावना n संख्याओं में से एक है, जो बहुत दुर्लभ है। हालाँकि, यह अभी भी वही कार्यावधि है जब विभाजन 50% -50% के स्थान पर 10% -90% है क्योंकि रिकर्सन ट्री की गहराई अभी भी Θ(''n''log''n'') होगी जिसमें रिकर्सन के प्रत्येक स्तर पर ''O''(''n'') समय लिया जाएगा।


=== [[आठ रानियों की समस्या]] के लिए यादृच्छिक लालची एल्गोरिदम ===
=== आठ क्वींस समस्या के लिए यादृच्छिक लुब्ध एल्गोरिथ्म ===
आठ रानियों की समस्या आमतौर पर बैकट्रैकिंग एल्गोरिदम से हल की जाती है। हालाँकि, लास वेगास एल्गोरिदम लागू किया जा सकता है; वास्तव में, यह बैकट्रैकिंग से अधिक कुशल है।
आठ क्वींस समस्या सामान्यतः पश्चअनुमार्गण एल्गोरिथ्म से हल की जाती है। हालाँकि, लास वेगास एल्गोरिथ्म लागू किया जा सकता है; वास्तव में, यह पश्चअनुमार्गण से अधिक कुशल है।


एक शतरंज की बिसात पर 8 रानियों को रखें ताकि कोई दूसरे पर हमला न करे। याद रखें कि रानी एक ही पंक्ति, स्तंभ और विकर्ण पर अन्य टुकड़ों पर हमला करती है।
एक शतरंज की बिसात पर 8 क्वींस को रखें ताकि कोई दूसरे पर आक्षेप न करे। याद रखें कि क्वींस एक ही पंक्ति, स्तंभ और विकर्ण पर अन्य टुकड़ों पर हमला करती है।


मान लें कि k पंक्तियाँ, 0 ≤ k ≤ 8, रानियों द्वारा सफलतापूर्वक कब्जा कर ली गई हैं।
मान लें कि k पंक्तियाँ, 0 ≤ k ≤ 8, क्वींस द्वारा सफलतापूर्वक ग्रहण कर ली गई हैं।


यदि k = 8 है, तो सफलता के साथ रुकें। अन्यथा, पंक्ति k + 1 पर कब्जा करने के लिए आगे बढ़ें।
यदि k = 8 है, तो सफलता के साथ रुकें। अन्यथा, पंक्ति k + 1 पर अधिकार करने के लिए आगे बढ़ें।


इस पंक्ति में मौजूदा रानियों द्वारा आक्रमण न किए गए सभी पदों की गणना करें। यदि कोई नहीं है, तो असफल हो जाइये। अन्यथा, यादृच्छिक रूप से एक चुनें, k बढ़ाएं और दोहराएं।
इस पंक्ति में उपस्थिता क्वींस द्वारा अधिकार न किए गए सभी पदों की गणना करें। अन्यथा, यादृच्छिक रूप से एक को चुनें, k बढ़ाएं और दोहराएं।


ध्यान दें कि यदि रानी को नहीं रखा जा सकता तो एल्गोरिदम विफल हो जाता है। लेकिन प्रक्रिया को दोहराया जा सकता है और हर बार अलग व्यवस्था उत्पन्न होगी।<ref>{{cite web |url = http://www.cs.man.ac.uk/~david/algorithms/randomizedAlgsSlides.pdf |title=यादृच्छिक एल्गोरिदम - एक संक्षिप्त परिचय|last=Barringer|first=Howard|date=December 2010 |website=www.cs.man.ac.uk |access-date=2018-12-08 }}</ref>
ध्यान दें कि यदि क्वींस को नहीं रखा जा सकता तो एल्गोरिथ्म विफल हो जाता है। लेकिन प्रक्रिया को दोहराया जा सकता है और हर बार अलग व्यवस्था उत्पन्न होगी। <ref>{{cite web |url = http://www.cs.man.ac.uk/~david/algorithms/randomizedAlgsSlides.pdf |title=यादृच्छिक एल्गोरिदम - एक संक्षिप्त परिचय|last=Barringer|first=Howard|date=December 2010 |website=www.cs.man.ac.uk |access-date=2018-12-08 }}</ref>




== [[जटिलता वर्ग]] ==
== [[जटिलता वर्ग]] ==
[[अपेक्षित मूल्य]] बहुपद रनटाइम के साथ लास वेगास एल्गोरिदम वाले [[निर्णय समस्या]]ओं की जटिलता वर्ग [[शून्य-त्रुटि संभाव्य बहुपद समय]] है।
[[अपेक्षित मूल्य]] बहुपद कार्यावधि के साथ लास वेगास एल्गोरिथ्म वाले [[निर्णय समस्या]]ओं की जटिलता वर्ग [[शून्य-त्रुटि संभाव्य बहुपद समय]] है।


यह पता चला है कि
यह पता चला है कि
: <math>\textsf{ZPP} = \textsf{RP} \cap \textsf{co-RP}</math>
: <math>\textsf{ZPP} = \textsf{RP} \cap \textsf{co-RP}</math>
जो कभी-कभी लास वेगास एल्गोरिदम के निर्माण के तरीके से गहराई से जुड़ा होता है। अर्थात् वर्ग [[आरपी (जटिलता)]] में सभी निर्णय समस्याएं शामिल हैं जिनके लिए एक यादृच्छिक बहुपद-समय एल्गोरिदम मौजूद है जो हमेशा सही उत्तर देता है जब सही उत्तर नहीं होता है, लेकिन उत्तर होने पर एक से दूर एक निश्चित संभावना के साथ गलत होने की अनुमति दी जाती है। हाँ । जब इस तरह का एल्गोरिदम किसी समस्या और उसके पूरक दोनों के लिए मौजूद होता है (हां और ना में उत्तरों की अदला-बदली के साथ), तो दोनों एल्गोरिदम को एक साथ और बार-बार चलाया जा सकता है: प्रत्येक को निरंतर संख्या में चरणों तक चलाएं, बारी-बारी से, जब तक कि उनमें से एक वापस न आ जाए निश्चित उत्तर. यह लास वेगास एल्गोरिदम बनाने का मानक तरीका है जो अपेक्षित बहुपद समय में चलता है। ध्यान दें कि सामान्य तौर पर लास वेगास एल्गोरिथम के रन टाइम पर कोई सबसे खराब स्थिति नहीं होती है।
जो कभी-कभी लास वेगास एल्गोरिथ्म के निर्माण के तरीके से गहराई से जुड़ा होता है। अर्थात् वर्ग [[आरपी (जटिलता)]] में सभी निर्णय समस्याएं सम्मिलित हैं जिनके लिए एक यादृच्छिक बहुपद-समय एल्गोरिथ्म उपस्थित है जो हमेशा सही उत्तर देता है जब सही उत्तर नहीं होता है, लेकिन उत्तर होने पर एक से दूर एक निश्चित संभावना के साथ गलत होने की अनुमति दी जाती है। जब इस तरह का एल्गोरिथ्म किसी समस्या और उसके पूरक दोनों के लिए उपस्थित होता है (हां और ना में उत्तरों की अदला-बदली के साथ), तो दोनों एल्गोरिथ्म को एक साथ और बार-बार चलाया जा सकता है: प्रत्येक को निरंतर संख्या में चरणों तक चलाएं, बारी-बारी से, जब तक कि उनमें से एक निश्चित उत्तर वापस न आ जाए। यह लास वेगास एल्गोरिथ्म बनाने का मानक तरीका है जो अपेक्षित बहुपद समय में चलता है। ध्यान दें कि सामान्यतः लास वेगास एल्गोरिथ्म के रन टाइम पर कोई सबसे खराब स्थिति नहीं होती है।


== इष्टतम लास वेगास एल्गोरिदम ==
== इष्टतम लास वेगास एल्गोरिथ्म ==
लास वेगास एल्गोरिदम को इष्टतम बनाने के लिए, अपेक्षित रन टाइम को कम से कम किया जाना चाहिए। यह इसके द्वारा किया जा सकता है:
लास वेगास एल्गोरिथ्म को इष्टतम बनाने के लिए, अपेक्षित रन टाइम को कम से कम किया जाना चाहिए। यह इसके द्वारा किया जा सकता है:
# लास वेगास एल्गोरिथ्म A(x) कुछ संख्या t के लिए बार-बार चलता है<sub>1</sub> कदम। यदि A(x) रन टाइम के दौरान रुक जाता है तो A(x) हो जाता है; अन्यथा, दूसरे चरण के लिए प्रक्रिया को शुरुआत से ही दोहराएं<sub>2</sub> कदम, इत्यादि।
# लास वेगास एल्गोरिथ्म A(x) कुछ संख्या t<sub>1</sub> चरण के लिए बार-बार चलता है। यदि A(x) रन टाइम के उपरान्त रुक जाता है तो A(x) हो जाता है; अन्यथा, दूसरे चरण t<sub>2</sub> चरण के लिए प्रक्रिया को प्रारम्भ से ही दोहराएं, इत्यादि।
# एक ऐसी रणनीति तैयार करना जो टी के वितरण के बारे में पूरी जानकारी देते हुए ए(एक्स) के लिए सभी रणनीतियों में से सबसे उपयुक्त हो<sub>A</sub>(एक्स)।
# एक ऐसी रणनीति तैयार करना जो T<sub>A</sub>(X) के वितरण के बारे में पूरी जानकारी देते हुए A(X) के लिए सभी रणनीतियों में से सबसे उपयुक्त हो।


इष्टतम रणनीति का अस्तित्व एक आकर्षक सैद्धांतिक अवलोकन हो सकता है। हालाँकि, वास्तविक जीवन में यह व्यावहारिक नहीं है क्योंकि टी के वितरण की जानकारी प्राप्त करना आसान नहीं है<sub>A</sub>(एक्स)। इसके अलावा, वितरण के बारे में जानकारी प्राप्त करने के लिए बार-बार प्रयोग चलाने का कोई मतलब नहीं है क्योंकि अधिकांश समय, किसी भी x के लिए उत्तर की केवल एक बार आवश्यकता होती है।<ref>{{cite journal |last=Luby |first=Michael |date=27 September 1993 |title=लास वेगास एल्गोरिदम का इष्टतम स्पीडअप|journal=Information Processing Letters|volume=47|issue=4 |pages=173–180|doi=10.1016/0020-0190(93)90029-9}}</ref>
इष्टतम रणनीति का अस्तित्व एक आकर्षक सैद्धांतिक अवलोकन हो सकता है। हालाँकि, वास्तविक जीवन में यह व्यावहारिक नहीं है क्योंकि T<sub>A</sub>(X) के वितरण की जानकारी प्राप्त करना आसान नहीं है। इसके अतिरिक्त, वितरण के बारे में जानकारी प्राप्त करने के लिए बार-बार प्रयोग चलाने का कोई अर्थ नहीं है क्योंकि अधिकांश समय, किसी भी x के लिए उत्तर की केवल एक बार आवश्यकता होती है। <ref>{{cite journal |last=Luby |first=Michael |date=27 September 1993 |title=लास वेगास एल्गोरिदम का इष्टतम स्पीडअप|journal=Information Processing Letters|volume=47|issue=4 |pages=173–180|doi=10.1016/0020-0190(93)90029-9}}</ref>




== मोंटे कार्लो एल्गोरिदम से संबंध ==
== मोंटे कार्लो एल्गोरिथ्म से संबंध ==
लास वेगास एल्गोरिदम की तुलना मोंटे कार्लो एल्गोरिदम से की जा सकती है, जिसमें उपयोग किए गए संसाधन सीमित हैं लेकिन उत्तर एक निश्चित (आमतौर पर छोटी) [[संभावना]] के साथ गलत हो सकता है। लास वेगास एल्गोरिदम को निर्धारित समय के लिए चलाकर और समाप्त होने में विफल होने पर यादृच्छिक उत्तर उत्पन्न करके मोंटे कार्लो एल्गोरिदम में परिवर्तित किया जा सकता है। मार्कोव की असमानता के अनुप्रयोग द्वारा, हम इस संभावना पर सीमा निर्धारित कर सकते हैं कि लास वेगास एल्गोरिथ्म निश्चित सीमा से अधिक हो जाएगा।
लास वेगास एल्गोरिथ्म की तुलना मोंटे कार्लो एल्गोरिथ्म से की जा सकती है, जिसमें उपयोग किए गए संसाधन सीमित हैं लेकिन उत्तर एक निश्चित (सामान्यतः छोटी) [[संभावना]] के साथ गलत हो सकता है। लास वेगास एल्गोरिथ्म को निर्धारित समय के लिए चलाकर और समाप्त होने में विफल होने पर यादृच्छिक उत्तर उत्पन्न करके मोंटे कार्लो एल्गोरिथ्म में परिवर्तित किया जा सकता है। मार्कोव की असमानता के अनुप्रयोग द्वारा, हम इस संभावना पर सीमा निर्धारित कर सकते हैं कि लास वेगास एल्गोरिथ्म निश्चित सीमा से अधिक हो जाएगा।


यहां लास वेगास और मोंटे कार्लो एल्गोरिदम की तुलना करने वाली एक तालिका है:<ref>Goodrich, Michael. ''Algorithm Design and Applications: Randomized Algorithms.'' Wiley, 2015'','' https://nscpolteksby.ac.id/ebook/files/Ebook/Computer%20Engineering/Algorithm%20Design%20and%20Applications%20A4%20(2015)/20.%20Chapter%2019%20-%20Randomized%20Algorithms.pdf. Oct 23, 2018.</ref>
यहां लास वेगास और मोंटे कार्लो एल्गोरिथ्म की तुलना करने वाली एक तालिका है: <ref>Goodrich, Michael. ''Algorithm Design and Applications: Randomized Algorithms.'' Wiley, 2015'','' https://nscpolteksby.ac.id/ebook/files/Ebook/Computer%20Engineering/Algorithm%20Design%20and%20Applications%20A4%20(2015)/20.%20Chapter%2019%20-%20Randomized%20Algorithms.pdf. Oct 23, 2018.</ref>
{| class="wikitable"
{| class="wikitable"
!
!
!Running Time
!संचालन समय
!Correctness
!सत्यता
|-
|-
|Las Vegas Algorithm
|लास वेगास एल्गोरिथ्म
|probabilistic
|प्रसंभाव्यतावादी
|certain
|निश्चित
|-
|-
|Monte Carlo Algorithm
|मोंटे कार्लो एल्गोरिथ्म
|certain
|निश्चित
|probabilistic
|प्रसंभाव्यतावादी
|}
|}
यदि शुद्धता का परीक्षण करने का एक नियतात्मक तरीका उपलब्ध है, तो मोंटे कार्लो एल्गोरिदम को लास वेगास एल्गोरिदम में बदलना संभव है। हालाँकि, एल्गोरिथम का परीक्षण करने के तरीके के बिना मोंटे कार्लो एल्गोरिथम को लास वेगास एल्गोरिथम में परिवर्तित करना कठिन है। दूसरी ओर, लास वेगास एल्गोरिदम को मोंटे कार्लो एल्गोरिदम में बदलना आसान है। यह कॉन्फिडेंस पैरामीटर द्वारा दी गई एक विशिष्ट अवधि के लिए लास वेगास एल्गोरिदम चलाकर किया जा सकता है। यदि एल्गोरिदम समय के भीतर समाधान ढूंढ लेता है, तो यह सफलता है और यदि नहीं, तो आउटपुट पर केवल खेद हो सकता है।
यदि शुद्धता का परीक्षण करने का एक नियतात्मक तरीका उपलब्ध है, तो मोंटे कार्लो एल्गोरिथ्म को लास वेगास एल्गोरिथ्म में बदलना संभव है। हालाँकि, एल्गोरिथ्म का परीक्षण करने के तरीके के बिना मोंटे कार्लो एल्गोरिथ्म को लास वेगास एल्गोरिथ्म में परिवर्तित करना कठिन है। दूसरी ओर, लास वेगास एल्गोरिथ्म को मोंटे कार्लो एल्गोरिथ्म में बदलना आसान है। यह कॉन्फिडेंस मापदण्ड द्वारा दी गई एक विशिष्ट अवधि के लिए लास वेगास एल्गोरिथ्म चलाकर किया जा सकता है। यदि एल्गोरिथ्म समय के भीतर समाधान ढूंढ लेता है, तो यह सफलता है और यदि नहीं, तो प्रक्षेपण पर केवल खेद हो सकता है।


तुलना के लिए यह लास वेगास और मोंटे कार्लो एल्गोरिदम का एक उदाहरण है:<ref>{{cite web |url = https://www.cs.cmu.edu/~arielpro/15251f15/slides/lec20.pdf |title = कंप्यूटर विज्ञान में महान सैद्धांतिक विचार|last=Procaccia |first = Ariel |date = 5 November 2015 |website = www.cs.cmu.edu |type = [[Microsoft PowerPoint|PowerPoint]]
तुलना के लिए यह लास वेगास और मोंटे कार्लो एल्गोरिथ्म का एक उदाहरण है:<ref>{{cite web |url = https://www.cs.cmu.edu/~arielpro/15251f15/slides/lec20.pdf |title = कंप्यूटर विज्ञान में महान सैद्धांतिक विचार|last=Procaccia |first = Ariel |date = 5 November 2015 |website = www.cs.cmu.edu |type = [[Microsoft PowerPoint|PowerPoint]]
|access-date = 3 November 2018 }}</ref>
|access-date = 3 November 2018 }}</ref>
मान लें कि सम n की लंबाई वाली एक सरणी है। सरणी में आधी प्रविष्टियाँ 0 हैं और शेष आधी 1 हैं। यहां लक्ष्य एक ऐसा सूचकांक ढूंढना है जिसमें 1 हो।
मान लें कि सम n की लंबाई वाली एक सरणी है। सरणी में आधी प्रविष्टियाँ 0 हैं और शेष आधी 1 हैं। यहां लक्ष्य एक ऐसा सूचकांक ढूंढना है जिसमें 1 हो।


Line 167: Line 164:
     return "Failed"
     return "Failed"
</syntaxhighlight>
</syntaxhighlight>
चूंकि लास वेगास तब तक समाप्त नहीं होता जब तक उसे सरणी में 1 नहीं मिल जाता, यह शुद्धता के साथ नहीं बल्कि रन-टाइम के साथ जुआ खेलता है। दूसरी ओर, मोंटे कार्लो 300 बार चलता है, जिसका अर्थ है कि यह जानना असंभव है कि मोंटे कार्लो 300 बार लूप के भीतर सरणी में 1 ढूंढेगा जब तक कि यह वास्तव में कोड निष्पादित न कर दे। इसका समाधान निकलेगा भी या नहीं. इसलिए, लास वेगास के विपरीत, मोंटे कार्लो रन-टाइम के साथ नहीं बल्कि शुद्धता के साथ जुआ खेलता है।
चूंकि लास वेगास तब तक समाप्त नहीं होता जब तक उसे सरणी में 1 नहीं मिल जाता, यह शुद्धता के साथ नहीं बल्कि रन-टाइम के साथ जुआ खेलता है। दूसरी ओर, मोंटे कार्लो 300 बार चलता है, जिसका अर्थ है कि यह जानना असंभव है कि मोंटे कार्लो 300 बार लूप के भीतर सरणी में 1 ढूंढेगा जब तक कि यह वास्तव में कूट निष्पादित न कर दे। इसका समाधान निकलेगा भी या नहीं। इसलिए, लास वेगास के विपरीत, मोंटे कार्लो रन-टाइम के साथ नहीं बल्कि शुद्धता के साथ जुआ खेलता है।


== यह भी देखें ==
== यह भी देखें ==
* मोंटे कार्लो एल्गोरिदम
* मोंटे कार्लो एल्गोरिथ्म
* [[अटलांटिक सिटी एल्गोरिदम]]
* [[अटलांटिक सिटी एल्गोरिदम|अटलांटिक सिटी एल्गोरिथ्म]]
* यादृच्छिकता
* यादृच्छिकता


Line 188: Line 185:
{{refend}}
{{refend}}


श्रेणी:यादृच्छिक एल्गोरिदम
श्रेणी:यादृच्छिक एल्गोरिथ्म
 


[[Category: Machine Translated Page]]
[[Category:Created On 30/06/2023]]
[[Category:Created On 30/06/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Webarchive template wayback links]]

Latest revision as of 11:10, 14 August 2023

कम्प्यूटिंग में, लास वेगास एल्गोरिथ्म एक यादृच्छिक एल्गोरिथ्म है जो हमेशा यथार्थ परिणाम देता है; अर्थात् यह सदैव सही परिणाम देता है अथवा असफलता की सूचना देता है। हालाँकि, लास वेगास एल्गोरिथ्म का कार्यावधि निविष्ट के आधार पर भिन्न होता है। लास वेगास एल्गोरिथ्म की सामान्य परिभाषा में यह प्रतिबंध सम्मिलित है कि अपेक्षित कार्यावधि सीमित होना चाहिए, जहां एल्गोरिथ्म में उपयोग की जाने वाली यादृच्छिक जानकारी, या एन्ट्रॉपी के स्थान पर किया जाता है। एक वैकल्पिक परिभाषा के लिए आवश्यक है कि लास वेगास एल्गोरिथ्म हमेशा समाप्त हो (प्रभावी विधि है), लेकिन समाधान खोजने में विफलता को इंगित करने के लिए एक आंशिक फलन प्रक्षेपण कर सकता है। [1] लास वेगास एल्गोरिथ्म की प्रकृति उन्हें उन स्थितियों में उपयुक्त बनाती है जहां संभावित समाधानों की संख्या सीमित है, और जहां किसी पदान्वेषी समाधान की शुद्धता की पुष्टि करना अपेक्षाकृत आसान है जबकि समाधान ढूंढना जटिल है।

लास वेगास एल्गोरिथ्म कृत्रिम बुद्धिमत्ता के क्षेत्र में और कंप्यूटर विज्ञान और संचालन अनुसंधान के अन्य क्षेत्रों में प्रमुख हैं। एआई में, स्टोकेस्टिक स्थानीय खोज (एसएलएस) एल्गोरिथ्म को लास वेगास प्रकार का माना जाता है। एसएलएस एल्गोरिथ्म का उपयोग एनपी-पूर्णता निर्णय समस्याओं और एनपी-कठोर संयुक्त अनुकूलन समस्याओं को संबोधित करने के लिए किया गया है। [2] हालाँकि, कुछ व्यवस्थित खोज विधियाँ, जैसे प्रस्तावात्मक संतुष्टि (एसएटी) के लिए डेविस-पुटनम एल्गोरिथ्म के आधुनिक संस्करण, गैर-नियतात्मक निर्णयों का भी उपयोग करते हैं, और इस प्रकार उन्हें लास वेगास एल्गोरिथ्म भी माना जा सकता है। [3]


इतिहास

लास वेगास एल्गोरिथ्म को 1979 में लास्ज़लो बाबई द्वारा आलेख समरूपता समस्या के संदर्भ में, मोंटे कार्लो एल्गोरिथ्म के दोहरे के रूप में प्रस्तुत किया गया था। [4] बाबई [5] सिक्का उछालने से जुड़े एक उदाहरण के साथ लास वेगास एल्गोरिथ्म शब्द प्रस्तुत किया गया: एल्गोरिथ्म स्वतंत्र सिक्का उछाल की एक श्रृंखला पर निर्भर करता है, और विफलता की एक छोटी संभावना है (कोई परिणाम नहीं)। हालाँकि, मोंटे कार्लो एल्गोरिथ्म के विपरीत, लास वेगास एल्गोरिथ्म किसी भी प्रतिवेदन किए गए परिणाम की शुद्धता की प्रत्याभुति दे सकता है।

उदाहरण

// Las Vegas algorithm
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;

जैसा कि ऊपर बताया गया है, लास वेगास एल्गोरिथ्म हमेशा सही परिणाम लौटाते हैं। उपरोक्त कूट इस संपत्ति को दर्शाता है। एक चर k यादृच्छिक रूप से उत्पन्न होता है; k उत्पन्न होने के बाद, k का उपयोग सरणी A को अनुक्रमित करने के लिए किया जाता है। यदि इस सूचकांक में मान 1 है, तो k वापस कर दिया जाता है; अन्यथा, एल्गोरिथ्म इस प्रक्रिया को तब तक दोहराता है जब तक कि उसे 1 नहीं मिल जाता। हालांकि यह लास वेगास एल्गोरिथ्म सही उत्तर खोजने की प्रत्याभुति देता है, लेकिन इसका कोई निश्चित कार्यावधि नहीं है; यादृच्छिकीकरण (उपरोक्त कूट की पंक्ति 3 में) के कारण, एल्गोरिथ्म समाप्त होने से पहले स्वेच्छाचारी ढंग से बहुत अधिक समय व्यतीत करना संभव है।

परिभाषा

यह अनुभाग वे स्थितियाँ प्रदान करता है जो किसी एल्गोरिथ्म के लास वेगास प्रकार के होने की विशेषता बताती हैं।

एक एल्गोरिथ्म A, समस्या वर्ग X के लिए एक लास वेगास एल्गोरिथ्म है, यदि [6]

  1. जब भी किसी दिए गए समस्या उदाहरण x∈X के लिए यह एक समाधान s लौटाता है, तो s को x का वैध समाधान होने की प्रत्याभुति दी जाती है।
  2. प्रत्येक दिए गए उदाहरण x पर, A का रन-टाइम एक यादृच्छिक चर RTA,x है।

लास वेगास एल्गोरिथ्म के लिए पूर्णता की तीन धारणाएँ हैं:

  • पूर्ण लास वेगास एल्गोरिथ्म को रन-टाइम Tmax के भीतर प्रत्येक हल करने योग्य समस्या को हल करने की प्रत्याभुति दी जा सकती है, जहां Tmax एक उदाहरण-निर्भर स्थिरांक है।

मान लीजिये P(RTA,x ≤ t) इस संभावना को निरूपित करें कि A घुलनशील उदाहरण X के लिए T के भीतर समय में एक समाधान ढूंढ लेता है, तो A बिल्कुल पूर्ण है यदि प्रत्येक X के लिए उपस्थित है

कुछ tmax इस प्रकार कि P(RTA,x ≤ tmax) = 1 है।

  • लगभग पूर्ण लास वेगास एल्गोरिथ्म प्रत्येक समस्या को 1 में परिवर्तित होने वाली संभावना के साथ हल करते हैं क्योंकि रन-टाइम अनंत तक पहुंचता है। इस प्रकार, A लगभग पूर्ण है, यदि प्रत्येक उदाहरण x के लिए, limt→∞ P(RTA,x ≤ t) = 1।
  • अनिवार्य रूप से अपूर्ण लास वेगास एल्गोरिथ्म लास वेगास एल्गोरिथ्म हैं जो लगभग पूर्ण नहीं हैं।

अनुमानित पूर्णता मुख्य रूप से सैद्धांतिक रुचि का विषय है, क्योंकि समाधान खोजने की समय सीमा सामान्यतः व्यावहारिक उपयोग के लिए बहुत बड़ी होती है।

अनुप्रयोग परिदृश्य

लास वेगास एल्गोरिथ्म में समस्या समायोजन के आधार पर मूल्यांकन के लिए अलग-अलग मानदंड हैं। इन मानदंडों को अलग-अलग समय सीमाओं के साथ तीन श्रेणियों में विभाजित किया गया है क्योंकि लास वेगास एल्गोरिथ्म में निर्धारित समय जटिलता नहीं है। यहां कुछ संभावित अनुप्रयोग परिदृश्य दिए गए हैं:

  • प्रकार 1: कोई समय सीमा नहीं है, जिसका अर्थ है कि एल्गोरिथ्म तब तक चलता है जब तक उसे समाधान नहीं मिल जाता।
  • प्रकार 2: परिणाम जानने के लिए एक समय सीमा tmax है।
  • प्रकार 3: किसी समाधान की उपयोगिता समाधान खोजने में लगने वाले समय से निर्धारित होती है।

(टाइप 1 और टाइप 2 टाइप 3 के विशेष स्तिथि हैं।)

टाइप 1 के लिए जहां कोई समय सीमा नहीं है, औसत रन-टाइम रन-टाइम व्यवहार का प्रतिनिधित्व कर सकता है। यह टाइप 2 के लिए समान मामला नहीं है।

यहाँ, P(RT ≤ tmax), जो समय के भीतर समाधान खोजने की संभावना है, इसके रन-टाइम व्यवहार का वर्णन करता है।

टाइप 3 कि स्तिथि में, इसके रन-टाइम व्यवहार को केवल रन-टाइम वियोजन फलन rtd द्वारा दर्शाया जा सकता है: R → [0,1] जिसे rtd(t) = P(RT ≤ t) या इसके सन्निकटन के रूप में परिभाषित किया गया है।

रन-टाइम वियोजन (आरटीडी) लास वेगास एल्गोरिथ्म के रन-टाइम व्यवहार का वर्णन करने का विशिष्ट तरीका है।

इस डेटा के साथ, हम आसानी से अन्य मानदंड प्राप्त कर सकते हैं जैसे कि औसत रन-टाइम, मानक विचलन, माध्यिका, प्रतिशत, या स्वेच्छाचारी समय-सीमा T के लिए सफलता संभावनाएं P(RT ≤ t) है।

अनुप्रयोग

सादृश्य

लास वेगास एल्गोरिथ्म खोज समस्याओं में प्रायः सामने आते हैं। उदाहरण के लिए, कोई व्यक्ति ऑनलाइन कुछ जानकारी खोज रहा है तो वह वांछित जानकारी के लिए संबंधित वेबसाइटों पर खोज कर सकता है। इस प्रकार समय की जटिलता भाग्यशाली होने और सामग्री को तुरंत ढूंढने से लेकर, दुर्भाग्यशाली होने और बड़ी मात्रा में समय खर्च करने तक होती है। एक बार सही वेबसाइट मिल जाए तो गलती की कोई संभावना नहीं रहती। [7]


यादृच्छिक क्विकसॉर्ट

INPUT: 
    # @o5grateful is an array of n elements
def randomized_quicksort(A): https://www.orionsarm.com/xcms.php?r=oaeg-fronthttps://www.orionsarm.com/xcms.php?r=oaeg-front
    if n == 1:
        return A  # A is sorted.
    else:
        i = random.randrange(1, n)  # Will take a random number in the range 1~n
        X = A[i]  # The pivot element
    """Partition A into elements < x, x, and >x  # as shown in the figure above.
    Execute Quicksort on A[1 to i-1] and A[i+1 to n].
    Combine the responses in order to obtain a sorted array."""

एक सरल उदाहरण यादृच्छिक क्विकॉर्ट है, जहां धुरी को यादृच्छिक रूप से चुना जाता है, और तत्वों को तीन विभाजनों में विभाजित करता है: धुरी से कम तत्व, धुरी के बराबर तत्व, और धुरी से बड़े तत्व हैं। यादृच्छिक क्विकॉर्ट के लिए बहुत सारे संसाधनों की आवश्यकता होती है लेकिन प्रक्षेपण के रूप में हमेशा क्रमबद्ध सरणी उत्पन्न होती है। [8] यह स्पष्ट है कि क्विकसॉर्ट हमेशा समाधान उत्पन्न करता है, जो इस स्तिथि में क्रमबद्ध सरणी है। दुर्भाग्य से, समय की जटिलता उतनी स्पष्ट नहीं है। यह पता चला है कि कार्यावधि इस बात पर निर्भर करता है कि हम किस तत्व को धुरी के रूप में चुनते हैं।

  • सबसे ख़राब स्थिति Θ(n2) जब धुरी सबसे छोटा या सबसे बड़ा तत्व हो।


  • हालाँकि, यादृच्छिकीकरण के माध्यम से, जहां धुरी को यादृच्छिक रूप से चुना जाता है और हर बार बिल्कुल मध्य मान होता है, क्विकसॉर्ट Θ(nlogn) में किया जा सकता है।

क्विकसॉर्ट का कार्यावधि काफी हद तक इस बात पर निर्भर करता है कि धुरी का चयन कितनी अच्छी तरह किया गया है। यदि धुरी का मान या तो बहुत बड़ा या छोटा है, तो विभाजन असंतुलित हो जाएगा, जिसके परिणामस्वरूप खराब कार्यावधि दक्षता होगी। हालाँकि, यदि धुरी का मान सरणी के मध्य के करीब है, तो विभाजन यथोचित रूप से संतुलित होगा, जिससे तीव्र कार्यावधि प्राप्त होती है। चूंकि धुरी को बेतरतीब ढंग से चुना गया है, इसलिए चलने का समय ज्यादातर समय अच्छा और कभी-कभी खराब होगा।

औसत स्तिथि में, यह निर्धारित करना कठिन है क्योंकि विश्लेषण निविष्ट वितरण पर नहीं बल्कि एल्गोरिथ्म द्वारा किए गए यादृच्छिक विकल्पों पर निर्भर करता है। क्विकसॉर्ट के औसत की गणना उन सभी संभावित यादृच्छिक विकल्पों पर की जाती है जो एल्गोरिथ्म धुरी चुनते समय बना सकता है।

हालाँकि सबसे खराब स्थिति वाला कार्यावधि Θ(n)2 है, औसत-केस कार्यावधि Θ(nlogn) है। यह पता चला है कि सबसे खराब स्थिति प्रायः नहीं होती है। n के बड़े मानों के लिए, कार्यावधि उच्च संभावना के साथ Θ(nlogn) है।

ध्यान दें कि हर बार धुरी के मध्य मान तत्व होने की संभावना n संख्याओं में से एक है, जो बहुत दुर्लभ है। हालाँकि, यह अभी भी वही कार्यावधि है जब विभाजन 50% -50% के स्थान पर 10% -90% है क्योंकि रिकर्सन ट्री की गहराई अभी भी Θ(nlogn) होगी जिसमें रिकर्सन के प्रत्येक स्तर पर O(n) समय लिया जाएगा।

आठ क्वींस समस्या के लिए यादृच्छिक लुब्ध एल्गोरिथ्म

आठ क्वींस समस्या सामान्यतः पश्चअनुमार्गण एल्गोरिथ्म से हल की जाती है। हालाँकि, लास वेगास एल्गोरिथ्म लागू किया जा सकता है; वास्तव में, यह पश्चअनुमार्गण से अधिक कुशल है।

एक शतरंज की बिसात पर 8 क्वींस को रखें ताकि कोई दूसरे पर आक्षेप न करे। याद रखें कि क्वींस एक ही पंक्ति, स्तंभ और विकर्ण पर अन्य टुकड़ों पर हमला करती है।

मान लें कि k पंक्तियाँ, 0 ≤ k ≤ 8, क्वींस द्वारा सफलतापूर्वक ग्रहण कर ली गई हैं।

यदि k = 8 है, तो सफलता के साथ रुकें। अन्यथा, पंक्ति k + 1 पर अधिकार करने के लिए आगे बढ़ें।

इस पंक्ति में उपस्थिता क्वींस द्वारा अधिकार न किए गए सभी पदों की गणना करें। अन्यथा, यादृच्छिक रूप से एक को चुनें, k बढ़ाएं और दोहराएं।

ध्यान दें कि यदि क्वींस को नहीं रखा जा सकता तो एल्गोरिथ्म विफल हो जाता है। लेकिन प्रक्रिया को दोहराया जा सकता है और हर बार अलग व्यवस्था उत्पन्न होगी। [9]


जटिलता वर्ग

अपेक्षित मूल्य बहुपद कार्यावधि के साथ लास वेगास एल्गोरिथ्म वाले निर्णय समस्याओं की जटिलता वर्ग शून्य-त्रुटि संभाव्य बहुपद समय है।

यह पता चला है कि

जो कभी-कभी लास वेगास एल्गोरिथ्म के निर्माण के तरीके से गहराई से जुड़ा होता है। अर्थात् वर्ग आरपी (जटिलता) में सभी निर्णय समस्याएं सम्मिलित हैं जिनके लिए एक यादृच्छिक बहुपद-समय एल्गोरिथ्म उपस्थित है जो हमेशा सही उत्तर देता है जब सही उत्तर नहीं होता है, लेकिन उत्तर होने पर एक से दूर एक निश्चित संभावना के साथ गलत होने की अनुमति दी जाती है। जब इस तरह का एल्गोरिथ्म किसी समस्या और उसके पूरक दोनों के लिए उपस्थित होता है (हां और ना में उत्तरों की अदला-बदली के साथ), तो दोनों एल्गोरिथ्म को एक साथ और बार-बार चलाया जा सकता है: प्रत्येक को निरंतर संख्या में चरणों तक चलाएं, बारी-बारी से, जब तक कि उनमें से एक निश्चित उत्तर वापस न आ जाए। यह लास वेगास एल्गोरिथ्म बनाने का मानक तरीका है जो अपेक्षित बहुपद समय में चलता है। ध्यान दें कि सामान्यतः लास वेगास एल्गोरिथ्म के रन टाइम पर कोई सबसे खराब स्थिति नहीं होती है।

इष्टतम लास वेगास एल्गोरिथ्म

लास वेगास एल्गोरिथ्म को इष्टतम बनाने के लिए, अपेक्षित रन टाइम को कम से कम किया जाना चाहिए। यह इसके द्वारा किया जा सकता है:

  1. लास वेगास एल्गोरिथ्म A(x) कुछ संख्या t1 चरण के लिए बार-बार चलता है। यदि A(x) रन टाइम के उपरान्त रुक जाता है तो A(x) हो जाता है; अन्यथा, दूसरे चरण t2 चरण के लिए प्रक्रिया को प्रारम्भ से ही दोहराएं, इत्यादि।
  2. एक ऐसी रणनीति तैयार करना जो TA(X) के वितरण के बारे में पूरी जानकारी देते हुए A(X) के लिए सभी रणनीतियों में से सबसे उपयुक्त हो।

इष्टतम रणनीति का अस्तित्व एक आकर्षक सैद्धांतिक अवलोकन हो सकता है। हालाँकि, वास्तविक जीवन में यह व्यावहारिक नहीं है क्योंकि TA(X) के वितरण की जानकारी प्राप्त करना आसान नहीं है। इसके अतिरिक्त, वितरण के बारे में जानकारी प्राप्त करने के लिए बार-बार प्रयोग चलाने का कोई अर्थ नहीं है क्योंकि अधिकांश समय, किसी भी x के लिए उत्तर की केवल एक बार आवश्यकता होती है। [10]


मोंटे कार्लो एल्गोरिथ्म से संबंध

लास वेगास एल्गोरिथ्म की तुलना मोंटे कार्लो एल्गोरिथ्म से की जा सकती है, जिसमें उपयोग किए गए संसाधन सीमित हैं लेकिन उत्तर एक निश्चित (सामान्यतः छोटी) संभावना के साथ गलत हो सकता है। लास वेगास एल्गोरिथ्म को निर्धारित समय के लिए चलाकर और समाप्त होने में विफल होने पर यादृच्छिक उत्तर उत्पन्न करके मोंटे कार्लो एल्गोरिथ्म में परिवर्तित किया जा सकता है। मार्कोव की असमानता के अनुप्रयोग द्वारा, हम इस संभावना पर सीमा निर्धारित कर सकते हैं कि लास वेगास एल्गोरिथ्म निश्चित सीमा से अधिक हो जाएगा।

यहां लास वेगास और मोंटे कार्लो एल्गोरिथ्म की तुलना करने वाली एक तालिका है: [11]

संचालन समय सत्यता
लास वेगास एल्गोरिथ्म प्रसंभाव्यतावादी निश्चित
मोंटे कार्लो एल्गोरिथ्म निश्चित प्रसंभाव्यतावादी

यदि शुद्धता का परीक्षण करने का एक नियतात्मक तरीका उपलब्ध है, तो मोंटे कार्लो एल्गोरिथ्म को लास वेगास एल्गोरिथ्म में बदलना संभव है। हालाँकि, एल्गोरिथ्म का परीक्षण करने के तरीके के बिना मोंटे कार्लो एल्गोरिथ्म को लास वेगास एल्गोरिथ्म में परिवर्तित करना कठिन है। दूसरी ओर, लास वेगास एल्गोरिथ्म को मोंटे कार्लो एल्गोरिथ्म में बदलना आसान है। यह कॉन्फिडेंस मापदण्ड द्वारा दी गई एक विशिष्ट अवधि के लिए लास वेगास एल्गोरिथ्म चलाकर किया जा सकता है। यदि एल्गोरिथ्म समय के भीतर समाधान ढूंढ लेता है, तो यह सफलता है और यदि नहीं, तो प्रक्षेपण पर केवल खेद हो सकता है।

तुलना के लिए यह लास वेगास और मोंटे कार्लो एल्गोरिथ्म का एक उदाहरण है:[12]

मान लें कि सम n की लंबाई वाली एक सरणी है। सरणी में आधी प्रविष्टियाँ 0 हैं और शेष आधी 1 हैं। यहां लक्ष्य एक ऐसा सूचकांक ढूंढना है जिसमें 1 हो। 

//Las Vegas algorithm
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;
        
//Monte Carlo algorithm
repeat 300 times:
    k = RandInt(n)
    if A[k] == 1
        return k
    return "Failed"

चूंकि लास वेगास तब तक समाप्त नहीं होता जब तक उसे सरणी में 1 नहीं मिल जाता, यह शुद्धता के साथ नहीं बल्कि रन-टाइम के साथ जुआ खेलता है। दूसरी ओर, मोंटे कार्लो 300 बार चलता है, जिसका अर्थ है कि यह जानना असंभव है कि मोंटे कार्लो 300 बार लूप के भीतर सरणी में 1 ढूंढेगा जब तक कि यह वास्तव में कूट निष्पादित न कर दे। इसका समाधान निकलेगा भी या नहीं। इसलिए, लास वेगास के विपरीत, मोंटे कार्लो रन-टाइम के साथ नहीं बल्कि शुद्धता के साथ जुआ खेलता है।

यह भी देखें

संदर्भ

उद्धरण

  1. ↑ Steven D. Galbraith (2012). सार्वजनिक कुंजी क्रिप्टोग्राफी का गणित. Cambridge University Press. p. 16. ISBN 978-1-107-01392-6.
  2. ↑ Selman, B., Kautz, H. A., & Cohen, B. “Local search strategies for satisfiability testing.” (1996).
  3. ↑ Hoos, Holger H.. “On the Empirical Evaluation of Las Vegas Algorithms — Position Paper.” (1998).
  4. ↑ * László Babai, Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D.M.S. No. 79-10.
  5. ↑ Babai, László. “Monte-Carlo algorithms in graph isomorphism testing.” (1979).
  6. ↑ H.H. Hoos and T. Stützle. Evaluating Las Vegas Algorithms — Pitfalls and Remedies. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI-98), pages 238–245. Morgan Kaufmann Publishers, San Francisco, CA, 1998.
  7. ↑ Randomized Algorithms. Brilliant.org. Retrieved 23:54, October 24, 2018, from https://brilliant.org/wiki/randomized-algorithms-overview/
  8. ↑ "From Las Vegas to Monte Carlo: Randomized Algorithms in Machine Learning Systems". Towards Data Science. 2018-09-07. Retrieved 2018-10-25.
  9. ↑ Barringer, Howard (December 2010). "यादृच्छिक एल्गोरिदम - एक संक्षिप्त परिचय" (PDF). www.cs.man.ac.uk. Retrieved 2018-12-08.
  10. ↑ Luby, Michael (27 September 1993). "लास वेगास एल्गोरिदम का इष्टतम स्पीडअप". Information Processing Letters. 47 (4): 173–180. doi:10.1016/0020-0190(93)90029-9.
  11. ↑ Goodrich, Michael. Algorithm Design and Applications: Randomized Algorithms. Wiley, 2015, https://nscpolteksby.ac.id/ebook/files/Ebook/Computer%20Engineering/Algorithm%20Design%20and%20Applications%20A4%20(2015)/20.%20Chapter%2019%20-%20Randomized%20Algorithms.pdf. Oct 23, 2018.
  12. ↑ Procaccia, Ariel (5 November 2015). "कंप्यूटर विज्ञान में महान सैद्धांतिक विचार" (PDF). www.cs.cmu.edu (PowerPoint). Retrieved 3 November 2018.


स्रोत

  • एल्गोरिदम और संगणना सिद्धांत हैंडबुक, सीआरसी प्रेस एलएलसी, 1999।
  • लास वेगास एल्गोरिथम, डिक्शनरी ऑफ एल्गोरिदम एंड डेटा स्ट्रक्चर्स में [ऑनलाइन], पॉल ई. ब्लैक, एड., यूएस मानक और प्रौद्योगिकी का राष्ट्रीय संस्थान 17 जुलाई 2006। (9 मई 2009 को अभिगमित) यहां उपलब्ध है: [1]

श्रेणी:यादृच्छिक एल्गोरिथ्म

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=लास_वेगास_एल्गोरिथ्म&oldid=245427’