पुनरावर्ती ब्याकट्रैकर भूलभुलैया जेनरेटर

रिकर्सिभ ब्याकट्र्याकर एल्गोरिथ्म वास्तवमा एक सामान्य उद्देश्य गहिराई-पहिलो खोज हो। भूलभुलैया उत्पादनको लागि प्रयोग गर्दा, यसलाई अनियमित रूपमा बाटो छनौट गर्न थोरै परिमार्जन गरिएको थियो, जबकि यदि वास्तविक खोज उद्देश्यका लागि प्रयोग गरियो भने, सामान्यतया प्रत्येक स्तरलाई रेखीय क्रममा खोजी गरिनेछ। यसले लामो, घुमाउरो कोरिडोरहरू र धेरै लामो, घुमाउरो समाधानको साथ भूलभुलैयाहरू उत्पादन गर्ने प्रवृत्ति राख्छ।

उत्तम भूलभुलैया भनेको त्यस्तो भूलभुलैया हो जहाँ भूलभुलैयाको कुनै पनि बिन्दुबाट अर्को कुनै पनि बिन्दुमा ठ्याक्कै एउटा बाटो हुन्छ। यसको मतलब तपाईं सर्कलमा घुम्न सक्नुहुन्न, तर तपाईंले प्रायः मृत छेउहरू भेट्नुहुनेछ, जसले गर्दा तपाईंलाई फर्केर फर्कन बाध्य पार्छ।

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

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

यसको नाम भएतापनि, यसलाई पुनरावृत्ति प्रयोग गरेर कार्यान्वयन गर्नु आवश्यक छैन। यो प्रायः LIFO क्यु (अर्थात् स्ट्याक) प्रयोग गरेर पुनरावृत्ति दृष्टिकोणमा लागू गरिन्छ। धेरै ठूला भूलभुलैयाहरूको लागि, पुनरावृत्ति प्रयोग गर्दा प्रोग्रामिङ भाषा र उपलब्ध मेमोरीमा निर्भर गर्दै कल स्ट्याक ओभरफ्लो हुने सम्भावना बढी हुन्छ। LIFO क्युलाई ठूलो मात्रामा डेटा ह्यान्डल गर्न, डिस्कमा वा डाटाबेसमा क्यु राख्नको लागि अझ सजिलै अनुकूलित गर्न सकिन्छ यदि उपलब्ध मेमोरी अपर्याप्त छ भने पनि।

यो कसरी काम गर्छ?

यो एल्गोरिथ्मले स्ट्याक-आधारित गहिराइ-पहिलो खोज दृष्टिकोण प्रयोग गरेर काम गर्छ। यहाँ चरण-दर-चरण ब्रेकडाउन छ:

1. सुरुवात कक्ष छान्नुहोस् र यसलाई भ्रमण गरिएको रूपमा चिन्ह लगाउनुहोस्।
2. भ्रमण नगरिएका कक्षहरू हुँदा: अहिलेसम्म भ्रमण नगरिएका छिमेकी कक्षहरू हेर्नुहोस्। यदि कम्तिमा एउटा भ्रमण नगरिएको छिमेकी अवस्थित छ भने: भ्रमण नगरिएका छिमेकीहरू मध्ये एउटालाई अनियमित रूपमा छनौट गर्नुहोस्। हालको कक्ष र छनौट गरिएको छिमेकी बीचको पर्खाल हटाउनुहोस्। छनौट गरिएको छिमेकीमा सार्नुहोस् र यसलाई भ्रमण गरिएको रूपमा चिन्ह लगाउनुहोस्। हालको कक्षलाई स्ट्याकमा धकेल्नुहोस्। यदि कुनै भ्रमण नगरिएको छिमेकीहरू अवस्थित छैनन् भने: स्ट्याकबाट अन्तिम सेल पप गरेर पछाडि जानुहोस्।
3. स्ट्याक खाली नभएसम्म यो प्रक्रिया जारी राख्नुहोस्।

यस एल्गोरिथ्मको बारेमा एउटा रोचक तथ्य यो हो कि यसले भूलभुलैया जेनरेटर र भूलभुलैया समाधानकर्ता दुवैको रूपमा काम गर्दछ। यदि तपाईंले यसलाई पहिले नै उत्पन्न गरिएको भूलभुलैयामा चलाउनुभयो र तपाईंले निर्धारित अन्तिम बिन्दुमा पुग्ने बित्तिकै रोकिनुभयो भने, स्ट्याकमा भूलभुलैयाको समाधान हुनेछ।

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

थप पढाइ

यदि तपाईंलाई यो पोस्ट मन पर्यो भने, तपाईंलाई यी सुझावहरू पनि मन पर्न सक्छन्:

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