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

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

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

इतिहास

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

उदाहरण

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

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

परिभाषा

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

एक कलन विधि A, समस्या वर्ग X के लिए एक लास वेगास कलन विधि है, यदि

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

इस डेटा के साथ, हम आसानी से अन्य मानदंड प्राप्त कर सकते हैं जैसे कि औसत रन-टाइम, मानक विचलन, माध्यिका, प्रतिशत, या स्वेच्छाचारी समय-सीमा 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% है क्योंकि रिकर्सन ट्री की गहराई अभी भी Θ(nlogn) होगी जिसमें रिकर्सन के प्रत्येक स्तर पर O(n) समय लिया जाएगा।

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

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

एक शतरंज की बिसात पर 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) हो जाता है; अन्यथा, दूसरे चरण t₂ चरण के लिए प्रक्रिया को प्रारम्भ से ही दोहराएं, इत्यादि।
2. एक ऐसी रणनीति तैयार करना जो T_A(X) के वितरण के बारे में पूरी जानकारी देते हुए A(X) के लिए सभी रणनीतियों में से सबसे उपयुक्त हो।

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

मोंटे कार्लो कलन विधि से संबंध

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

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

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

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

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

मान लें कि सम 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]

श्रेणी:यादृच्छिक कलन विधि