रिकर्सिव बैकट्रैकर भूलभुलैया जनरेटर

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

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

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

रिकर्सिव बैकट्रैकर एल्गोरिदम एक डेप्थ-फर्स्ट सर्च तरीका है जिससे परफेक्ट मेज़ (ऐसी मेज़ जिसमें कोई लूप न हो और किन्हीं दो पॉइंट्स के बीच एक ही रास्ता हो) बनते हैं। यह आसान, असरदार है, और लंबे, घुमावदार कॉरिडोर वाले देखने में अच्छे मेज़ बनाता है।

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

यह काम किस प्रकार करता है

एल्गोरिदम स्टैक-बेस्ड डेप्थ-फर्स्ट सर्च अप्रोच का इस्तेमाल करके काम करता है। यहाँ स्टेप-बाय-स्टेप ब्रेकडाउन दिया गया है:

1. एक शुरुआती सेल चुनें और उसे विज़िट किया हुआ मार्क करें।
2. जब ऐसे सेल हों जिन पर अभी तक विज़िट नहीं किया गया है: आस-पास के उन सेल को देखें जिन पर अभी तक विज़िट नहीं किया गया है। अगर कम से कम एक ऐसा पड़ोसी है जिस पर विज़िट नहीं किया गया है: रैंडम तरीके से किसी एक पड़ोसी को चुनें जिस पर विज़िट नहीं किया गया है। मौजूदा सेल और चुने हुए पड़ोसी के बीच की दीवार हटा दें। चुने हुए पड़ोसी के पास जाएं और उसे विज़िट किया हुआ मार्क करें। मौजूदा सेल को स्टैक पर पुश करें। अगर कोई ऐसा पड़ोसी नहीं है जिस पर विज़िट नहीं किया गया है: स्टैक से आखिरी सेल को पॉप करके बैकट्रैक करें।
3. इस प्रोसेस को तब तक जारी रखें जब तक स्टैक खाली न हो जाए।

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

असल में, इस साइट पर इस एल्गोरिदम के दो वर्शन हैं: एक LIFO क्यू बेस्ड, जो इस पेज पर मेज़ बनाने के लिए है और एक रिकर्सन बेस्ड, जो मेज़ को सॉल्व करने के लिए है, और दूसरे एल्गोरिदम से बनने वाले मेज़ भी (इसी तरह सॉल्यूशन वाले मैप बनते हैं)। दो अलग-अलग वर्शन होना सिर्फ़ मज़े के लिए है क्योंकि मैं एक नर्ड हूँ जिसे यह इंटरेस्टिंग लगता है, कोई भी दोनों के लिए काम कर सकता था ;-)

अग्रिम पठन

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

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