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

From Vigyanwiki
(text)
No edit summary
 
(3 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> लास वेगास एल्गोरिथ्म की प्रकृति उन्हें उन स्थितियों में उपयुक्त बनाती है जहां संभावित समाधानों की संख्या सीमित है, और जहां किसी पदान्वेषी समाधान की शुद्धता की पुष्टि करना अपेक्षाकृत आसान है जबकि समाधान ढूंढना जटिल है।


लास वेगास कलन विधि कृत्रिम बुद्धिमत्ता के क्षेत्र में और कंप्यूटर विज्ञान और संचालन अनुसंधान के अन्य क्षेत्रों में प्रमुख हैं। एआई में, [[स्टोकेस्टिक स्थानीय खोज]] (एसएलएस) कलन विधि को लास वेगास प्रकार का माना जाता है। एसएलएस कलन विधि का उपयोग एनपी-पूर्णता निर्णय समस्याओं और एनपी-कठोर संयुक्त अनुकूलन समस्याओं को संबोधित करने के लिए किया गया है। <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>
लास वेगास एल्गोरिथ्म कृत्रिम बुद्धिमत्ता के क्षेत्र में और कंप्यूटर विज्ञान और संचालन अनुसंधान के अन्य क्षेत्रों में प्रमुख हैं। एआई में, [[स्टोकेस्टिक स्थानीय खोज]] (एसएलएस) एल्गोरिथ्म को लास वेगास प्रकार का माना जाता है। एसएलएस एल्गोरिथ्म का उपयोग एनपी-पूर्णता निर्णय समस्याओं और एनपी-कठोर संयुक्त अनुकूलन समस्याओं को संबोधित करने के लिए किया गया है। <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> सिक्का उछालने से जुड़े एक उदाहरण के साथ लास वेगास एल्गोरिथ्म शब्द प्रस्तुत किया गया: एल्गोरिथ्म स्वतंत्र सिक्का उछाल की एक श्रृंखला पर निर्भर करता है, और विफलता की एक छोटी संभावना है (कोई परिणाम नहीं)। हालाँकि, मोंटे कार्लो एल्गोरिथ्म के विपरीत, लास वेगास एल्गोरिथ्म किसी भी प्रतिवेदन किए गए परिणाम की शुद्धता की प्रत्याभुति दे सकता है।


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


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


एक कलन विधि 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>
एक एल्गोरिथ्म 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> है।
लास वेगास कलन विधि के लिए पूर्णता की तीन धारणाएँ हैं:
लास वेगास एल्गोरिथ्म के लिए पूर्णता की तीन धारणाएँ हैं:


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


मान लीजिये P(RT<sub>A,x</sub> ≤ t) इस संभावना को निरूपित करें कि A घुलनशील उदाहरण X के लिए T के भीतर समय में एक समाधान ढूंढ लेता है, तो A बिल्कुल पूर्ण है यदि प्रत्येक X के लिए उपस्थित है
मान लीजिये P(RT<sub>A,x</sub> ≤ t) इस संभावना को निरूपित करें कि A घुलनशील उदाहरण X के लिए T के भीतर समय में एक समाधान ढूंढ लेता है, तो A बिल्कुल पूर्ण है यदि प्रत्येक X के लिए उपस्थित है
Line 31: Line 31:
कुछ t<small>max</small> इस प्रकार कि P(RT<sub>A,x</sub> ≤ t<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> P(RT<sub>A,x</sub> ≤ t) = 1।
* लगभग पूर्ण लास वेगास एल्गोरिथ्म प्रत्येक समस्या को 1 में परिवर्तित होने वाली संभावना के साथ हल करते हैं क्योंकि रन-टाइम अनंत तक पहुंचता है। इस प्रकार, A लगभग पूर्ण है, यदि प्रत्येक उदाहरण x के लिए, lim<sub>t→∞</sub> P(RT<sub>A,x</sub> ≤ t) = 1।
* अनिवार्य रूप से अपूर्ण लास वेगास कलन विधि लास वेगास कलन विधि हैं जो लगभग पूर्ण नहीं हैं।
* अनिवार्य रूप से अपूर्ण लास वेगास एल्गोरिथ्म लास वेगास एल्गोरिथ्म हैं जो लगभग पूर्ण नहीं हैं।


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


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


*प्रकार 1: कोई समय सीमा नहीं है, जिसका अर्थ है कि कलन विधि तब तक चलता है जब तक उसे समाधान नहीं मिल जाता।
*प्रकार 1: कोई समय सीमा नहीं है, जिसका अर्थ है कि एल्गोरिथ्म तब तक चलता है जब तक उसे समाधान नहीं मिल जाता।
*प्रकार 2: परिणाम जानने के लिए एक समय सीमा t<sub>max</sub> है।
*प्रकार 2: परिणाम जानने के लिए एक समय सीमा t<sub>max</sub> है।
*प्रकार 3: किसी समाधान की उपयोगिता समाधान खोजने में लगने वाले समय से निर्धारित होती है।
*प्रकार 3: किसी समाधान की उपयोगिता समाधान खोजने में लगने वाले समय से निर्धारित होती है।
Line 51: Line 51:
टाइप 3 कि स्तिथि में, इसके रन-टाइम व्यवहार को केवल रन-टाइम वियोजन फलन rtd द्वारा दर्शाया जा सकता है: R → [0,1] जिसे rtd(t) = P(RT ≤ t) या इसके सन्निकटन के रूप में परिभाषित किया गया है।
टाइप 3 कि स्तिथि में, इसके रन-टाइम व्यवहार को केवल रन-टाइम वियोजन फलन rtd द्वारा दर्शाया जा सकता है: R → [0,1] जिसे rtd(t) = P(RT ≤ t) या इसके सन्निकटन के रूप में परिभाषित किया गया है।


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


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


=== सादृश्य ===
=== सादृश्य ===
लास वेगास कलन विधि [[खोज समस्या]]ओं में प्रायः सामने आते हैं। उदाहरण के लिए, कोई व्यक्ति ऑनलाइन कुछ जानकारी खोज रहा है तो वह वांछित जानकारी के लिए संबंधित वेबसाइटों पर खोज कर सकता है। इस प्रकार समय की जटिलता भाग्यशाली होने और सामग्री को तुरंत ढूंढने से लेकर, दुर्भाग्यशाली होने और बड़ी मात्रा में समय खर्च करने तक होती है। एक बार सही वेबसाइट मिल जाए तो गलती की कोई संभावना नहीं रहती। <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 91: Line 91:
क्विकसॉर्ट का कार्यावधि काफी हद तक इस बात पर निर्भर करता है कि धुरी का चयन कितनी अच्छी तरह किया गया है। यदि धुरी का मान या तो बहुत बड़ा या छोटा है, तो विभाजन असंतुलित हो जाएगा, जिसके परिणामस्वरूप खराब कार्यावधि दक्षता होगी। हालाँकि, यदि धुरी का मान सरणी के मध्य के करीब है, तो विभाजन यथोचित रूप से संतुलित होगा, जिससे तीव्र कार्यावधि प्राप्त होती है। चूंकि धुरी को बेतरतीब ढंग से चुना गया है, इसलिए चलने का समय ज्यादातर समय अच्छा और कभी-कभी खराब होगा।
क्विकसॉर्ट का कार्यावधि काफी हद तक इस बात पर निर्भर करता है कि धुरी का चयन कितनी अच्छी तरह किया गया है। यदि धुरी का मान या तो बहुत बड़ा या छोटा है, तो विभाजन असंतुलित हो जाएगा, जिसके परिणामस्वरूप खराब कार्यावधि दक्षता होगी। हालाँकि, यदि धुरी का मान सरणी के मध्य के करीब है, तो विभाजन यथोचित रूप से संतुलित होगा, जिससे तीव्र कार्यावधि प्राप्त होती है। चूंकि धुरी को बेतरतीब ढंग से चुना गया है, इसलिए चलने का समय ज्यादातर समय अच्छा और कभी-कभी खराब होगा।


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


हालाँकि सबसे खराब स्थिति वाला कार्यावधि Θ(n)<sup>2</sup> है, औसत-केस कार्यावधि Θ(nlogn) है। यह पता चला है कि सबसे खराब स्थिति प्रायः नहीं होती है। n के बड़े मानों के लिए, कार्यावधि उच्च संभावना के साथ Θ(nlogn) है।
हालाँकि सबसे खराब स्थिति वाला कार्यावधि Θ(n)<sup>2</sup> है, औसत-केस कार्यावधि Θ(nlogn) है। यह पता चला है कि सबसे खराब स्थिति प्रायः नहीं होती है। n के बड़े मानों के लिए, कार्यावधि उच्च संभावना के साथ Θ(nlogn) है।
Line 97: Line 97:
ध्यान दें कि हर बार धुरी के मध्य मान तत्व होने की संभावना n संख्याओं में से एक है, जो बहुत दुर्लभ है। हालाँकि, यह अभी भी वही कार्यावधि है जब विभाजन 50% -50% के स्थान पर 10% -90% है क्योंकि रिकर्सन ट्री की गहराई अभी भी Θ(''n''log''n'') होगी जिसमें रिकर्सन के प्रत्येक स्तर पर ''O''(''n'') समय लिया जाएगा।
ध्यान दें कि हर बार धुरी के मध्य मान तत्व होने की संभावना n संख्याओं में से एक है, जो बहुत दुर्लभ है। हालाँकि, यह अभी भी वही कार्यावधि है जब विभाजन 50% -50% के स्थान पर 10% -90% है क्योंकि रिकर्सन ट्री की गहराई अभी भी Θ(''n''log''n'') होगी जिसमें रिकर्सन के प्रत्येक स्तर पर ''O''(''n'') समय लिया जाएगा।


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


एक शतरंज की बिसात पर 8 क्वींस को रखें ताकि कोई दूसरे पर आक्षेप न करे। याद रखें कि क्वींस एक ही पंक्ति, स्तंभ और विकर्ण पर अन्य टुकड़ों पर हमला करती है।
एक शतरंज की बिसात पर 8 क्वींस को रखें ताकि कोई दूसरे पर आक्षेप न करे। याद रखें कि क्वींस एक ही पंक्ति, स्तंभ और विकर्ण पर अन्य टुकड़ों पर हमला करती है।
Line 108: Line 108:
इस पंक्ति में उपस्थिता क्वींस द्वारा अधिकार न किए गए सभी पदों की गणना करें। अन्यथा, यादृच्छिक रूप से एक को चुनें, 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) हो जाता है; अन्यथा, दूसरे चरण t<sub>2</sub> चरण के लिए प्रक्रिया को प्रारम्भ से ही दोहराएं, इत्यादि।
# लास वेगास एल्गोरिथ्म A(x) कुछ संख्या t<sub>1</sub> चरण के लिए बार-बार चलता है। यदि A(x) रन टाइम के उपरान्त रुक जाता है तो A(x) हो जाता है; अन्यथा, दूसरे चरण t<sub>2</sub> चरण के लिए प्रक्रिया को प्रारम्भ से ही दोहराएं, इत्यादि।
# एक ऐसी रणनीति तैयार करना जो T<sub>A</sub>(X) के वितरण के बारे में पूरी जानकारी देते हुए A(X) के लिए सभी रणनीतियों में से सबसे उपयुक्त हो।
# एक ऐसी रणनीति तैयार करना जो T<sub>A</sub>(X) के वितरण के बारे में पूरी जानकारी देते हुए A(X) के लिए सभी रणनीतियों में से सबसे उपयुक्त हो।


Line 126: Line 126:




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


यहां लास वेगास और मोंटे कार्लो कलन विधि की तुलना करने वाली एक तालिका है:<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"
!
!
Line 135: Line 135:
!सत्यता
!सत्यता
|-
|-
|लास वेगास कलन विधि
|लास वेगास एल्गोरिथ्म
|प्रसंभाव्यतावादी
|प्रसंभाव्यतावादी
|निश्चित
|निश्चित
|-
|-
|मोंटे कार्लो कलन विधि
|मोंटे कार्लो एल्गोरिथ्म
|निश्चित
|निश्चित
|प्रसंभाव्यतावादी
|प्रसंभाव्यतावादी
|}
|}
यदि शुद्धता का परीक्षण करने का एक नियतात्मक तरीका उपलब्ध है, तो मोंटे कार्लो कलन विधि को लास वेगास कलन विधि में बदलना संभव है। हालाँकि, कलन विधि का परीक्षण करने के तरीके के बिना मोंटे कार्लो कलन विधि को लास वेगास कलन विधि में परिवर्तित करना कठिन है। दूसरी ओर, लास वेगास कलन विधि को मोंटे कार्लो कलन विधि में बदलना आसान है। यह कॉन्फिडेंस मापदण्ड द्वारा दी गई एक विशिष्ट अवधि के लिए लास वेगास कलन विधि चलाकर किया जा सकता है। यदि कलन विधि समय के भीतर समाधान ढूंढ लेता है, तो यह सफलता है और यदि नहीं, तो प्रक्षेपण पर केवल खेद हो सकता है।
यदि शुद्धता का परीक्षण करने का एक नियतात्मक तरीका उपलब्ध है, तो मोंटे कार्लो एल्गोरिथ्म को लास वेगास एल्गोरिथ्म में बदलना संभव है। हालाँकि, एल्गोरिथ्म का परीक्षण करने के तरीके के बिना मोंटे कार्लो एल्गोरिथ्म को लास वेगास एल्गोरिथ्म में परिवर्तित करना कठिन है। दूसरी ओर, लास वेगास एल्गोरिथ्म को मोंटे कार्लो एल्गोरिथ्म में बदलना आसान है। यह कॉन्फिडेंस मापदण्ड द्वारा दी गई एक विशिष्ट अवधि के लिए लास वेगास एल्गोरिथ्म चलाकर किया जा सकता है। यदि एल्गोरिथ्म समय के भीतर समाधान ढूंढ लेता है, तो यह सफलता है और यदि नहीं, तो प्रक्षेपण पर केवल खेद हो सकता है।


तुलना के लिए यह लास वेगास और मोंटे कार्लो कलन विधि का एक उदाहरण है:<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>


Line 167: Line 167:


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


Line 185: 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’