लास वेगास एल्गोरिथ्म

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

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

इतिहास

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

उदाहरण

<सिंटैक्सहाइलाइट लैंग= जावा लाइन= 1 > // लास वेगास एल्गोरिदम दोहराना:

   के = रैंडइंट (एन)
   यदि ए[के] == 1,
       वापसी क;

</सिंटैक्सहाइलाइट>

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

परिभाषा

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

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

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

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

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

चलो पी(आरटी_A,x ≤ टी) इस संभावना को निरूपित करें कि ए घुलनशील उदाहरण एक्स के लिए टी के भीतर समय में एक समाधान ढूंढ लेता है, तो ए बिल्कुल पूर्ण है यदि प्रत्येक एक्स के लिए मौजूद है

कुछ टीmax ऐसा कि P(RT_A,x ≤ टी_max) = 1.

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

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

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

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

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

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

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

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

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

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

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

अनुप्रयोग

सादृश्य

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

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

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."""

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

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

$T(n)=T(0)+T(n-1)+\Theta (n)$

$T(n)=\Theta (1)+T(n-1)+\Theta (n)$

$T(n)=T(n-1)+\Theta (n)$

$T(n)=\Theta (n^{2})$

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

$T(n)\leq 2*T(n/2)+\Theta (n)$

$T(n)=\Theta (n\log(n))$

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

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

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

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

आठ रानियों की समस्या के लिए यादृच्छिक लालची एल्गोरिदम

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

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

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

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

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

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

जटिलता वर्ग

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

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

${\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}$

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

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

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

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

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

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

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

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

	Running Time	Correctness
Las Vegas Algorithm	probabilistic	certain
Monte Carlo Algorithm	certain	probabilistic

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

तुलना के लिए यह लास वेगास और मोंटे कार्लो एल्गोरिदम का एक उदाहरण है: मान लें कि सम 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 ढूंढेगा जब तक कि यह वास्तव में कोड निष्पादित न कर दे। इसका समाधान निकलेगा भी या नहीं. इसलिए, लास वेगास के विपरीत, मोंटे कार्लो रन-टाइम के साथ नहीं बल्कि शुद्धता के साथ जुआ खेलता है।

यह भी देखें

• मोंटे कार्लो एल्गोरिदम
• अटलांटिक सिटी एल्गोरिदम
• यादृच्छिकता

संदर्भ

स्रोत

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

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