विल्सन का एल्गोरिदम भूलभुलैया जनरेटर

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

एक आदर्श भूलभुलैया वह भूलभुलैया होती है जिसमें भूलभुलैया के किसी भी बिंदु से किसी अन्य बिंदु तक जाने के लिए बिल्कुल एक ही रास्ता होता है। इसका मतलब है कि आप चक्कर लगाते हुए नहीं रह सकते, लेकिन आप अक्सर ऐसे रास्ते पर आएँगे जहाँ आपको पीछे मुड़ना होगा और वापस लौटना होगा।

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

विल्सन के एल्गोरिदम के बारे में

लूप-इरेज्ड रैंडम वॉल का इस्तेमाल करके यूनिफ़ॉर्म स्पैनिंग ट्री बनाने के लिए विल्सन का एल्गोरिदम डेविड ब्रूस विल्सन ने बनाया था।

विल्सन ने असल में यह एल्गोरिदम 1996 में तब शुरू किया था जब वे प्रोबेबिलिटी थ्योरी में रैंडम स्पैनिंग ट्री और मार्कोव चेन पर रिसर्च कर रहे थे। हालांकि उनका काम ज़्यादातर मैथ और स्टैटिस्टिकल फ़िज़िक्स में था, लेकिन तब से इस एल्गोरिदम को मेज़ बनाने के लिए बड़े पैमाने पर अपनाया गया है क्योंकि यह एकदम एक जैसी मेज़ बना सकता है।

विल्सन का एल्गोरिदम मेज़ जेनरेशन के लिए कैसे काम करता है

विल्सन का एल्गोरिदम यह पक्का करता है कि आखिरी मेज़ बिना किसी लूप के पूरी तरह से कनेक्टेड हो, यह रैंडम वॉक का इस्तेमाल करके बिना विज़िट किए गए सेल्स से बार-बार रास्ते बनाता है।

चरण 1: आरंभ करें

• दीवारों से भरे ग्रिड से शुरू करें।
• सभी संभावित पैसेज सेल की एक लिस्ट बनाएं।

स्टेप 2: एक रैंडम शुरुआती सेल चुनें

• कोई भी रैंडम सेल चुनें और उसे विज़िट किया हुआ मार्क करें। यह जेनरेशन के दौरान मेज़ का शुरुआती पॉइंट होता है।

स्टेप 3: लूप-इरेज़िंग के साथ रैंडम वॉक

• एक ऐसा सेल चुनें जहां लोग नहीं गए हैं और रैंडम वॉक (रैंडम दिशाओं में चलना) शुरू करें।
• अगर वॉक किसी पहले से विज़िट किए गए सेल तक पहुँचता है, तो रास्ते में किसी भी लूप को मिटा दें।
• एक बार जब वॉक विज़िट किए गए इलाके से कनेक्ट हो जाए, तो रास्ते में सभी सेल को विज़िट किया हुआ मार्क कर दें।

स्टेप 4: सभी सेल विज़िट होने तक दोहराएं:

• अनविज़िटेड सेल्स को चुनते रहें और रैंडम वॉक करते रहें जब तक कि हर सेल मेज़ का हिस्सा न बन जाए।

अग्रिम पठन

यदि आपको यह पोस्ट पसंद आई हो, तो आपको ये सुझाव भी पसंद आ सकते हैं:

• बढ़ते पेड़ एल्गोरिथ्म भूलभुलैया जनरेटर
• रिकर्सिव बैकट्रैकर भूलभुलैया जनरेटर
• क्रुस्कल का एल्गोरिदम भूलभुलैया जनरेटर