रिकर्सिव्ह बॅकट्रॅकर मेझ जनरेटर

पुनरावर्ती बॅकट्रॅकर अल्गोरिदम खरोखर एक सामान्य हेतू खोली-प्रथम शोध आहे. जेव्हा चक्रव्यूह निर्मितीसाठी वापरले जाते, तेव्हा यादृच्छिकपणे मार्ग निवडण्यासाठी त्यात किंचित बदल केला जातो, तर प्रत्यक्ष शोध हेतूंसाठी वापरल्यास, सामान्यत: प्रत्येक स्तर रेखीय क्रमाने शोधला जातो. लांब, वळणदार कॉरिडॉर आणि खूप लांब, वळणदार द्रावण असलेले चक्रव्यूह तयार करण्याकडे त्याचा कल असतो.

परिपूर्ण भूलभुलैया म्हणजे असा भूलभुलैया ज्यामध्ये भूलभुलैयामधील कोणत्याही बिंदूपासून दुसऱ्या बिंदूपर्यंत एकच मार्ग असतो. याचा अर्थ असा की तुम्ही वर्तुळात फिरू शकत नाही, परंतु तुम्हाला अनेकदा अडचणी येतील, ज्यामुळे तुम्हाला मागे वळून परत जावे लागेल.

येथे तयार केलेल्या भूलभुलैया नकाशांमध्ये कोणत्याही सुरुवातीच्या आणि शेवटच्या स्थानांशिवाय डीफॉल्ट आवृत्ती समाविष्ट आहे, म्हणून तुम्ही ते स्वतः ठरवू शकता: भूलभुलैयामधील कोणत्याही बिंदूपासून इतर कोणत्याही बिंदूपर्यंत एक उपाय असेल. जर तुम्हाला प्रेरणा हवी असेल, तर तुम्ही सुचविलेले प्रारंभ आणि शेवटचे स्थान सक्षम करू शकता - आणि दोघांमधील उपाय देखील पाहू शकता.

पुनरावर्ती बॅकट्रॅकर अल्गोरिदम ही परिपूर्ण चक्रव्यूह (लूप नसलेले चक्रव्यूह आणि कोणत्याही दोन बिंदूंमधील एकच मार्ग असलेले चक्रव्यूह) तयार करण्यासाठी एक खोली-प्रथम शोध पद्धत आहे. हे सोपे, कार्यक्षम आहे आणि लांब, वळणदार कॉरिडॉरसह दृष्टीस आकर्षक चक्रव्यूह तयार करते.

त्याचे नाव असूनही, पुनरावृत्तीचा वापर करून त्याची अंमलबजावणी करणे आवश्यक नाही. हे बर्याचदा एलआयएफओ रांग (म्हणजे स्टॅक) वापरुन पुनरावृत्ती पध्दतीने अंमलात आणले जाते. खूप मोठ्या चक्रव्यूहासाठी, पुनरावृत्ती वापरल्याने प्रोग्रामिंग भाषा आणि उपलब्ध मेमरीवर अवलंबून कॉल स्टॅक ओव्हरफ्लो होण्याची शक्यता असते. उपलब्ध मेमरी अपुरी असल्यास डिस्कवर किंवा डेटाबेसमध्ये रांग ठेवणे देखील मोठ्या प्रमाणात डेटा हाताळण्यासाठी एलआयएफओ रांग अधिक सहजपणे अनुकूलित केली जाऊ शकते.

हे कसे कार्य करते

अल्गोरिदम स्टॅक-आधारित डेप्थ-फर्स्ट सर्च दृष्टिकोन वापरून कार्य करते. चरण-दर-चरण ब्रेकडाउन येथे आहे:

1. सुरुवातीचा सेल निवडा आणि भेट दिल्याप्रमाणे चिन्हांकित करा.
2. तेथे न पाहिलेल्या पेशी असताना:
   • शेजारच्या पेशींकडे पहा ज्यांना अद्याप भेट दिली गेली नाही.
   • जर कमीतकमी एक न पाहिलेला शेजारी अस्तित्वात असेल तर:
     • न पाहिलेल्या शेजाऱ्यांपैकी एकाची निवड करा.
     • सध्याचा सेल आणि निवडलेला शेजारी यांच्यामधील भिंत काढून टाका.
     • निवडलेल्या शेजाऱ्याकडे जा आणि भेट दिल्याप्रमाणे चिन्हांकित करा.
     • सध्याच्या सेलला स्टॅकवर ढकलून द्या.
   • भेट न दिलेले शेजारी अस्तित्वात नसल्यास:
     • स्टॅकमधून शेवटचा सेल पॉप करून बॅकट्रॅक करा.
3. स्टॅक रिकामा होईपर्यंत ही प्रक्रिया सुरू ठेवा.

या अल्गोरिदमबद्दल एक मनोरंजक तथ्य म्हणजे हे चक्रव्यूह जनरेटर आणि चक्रव्यूह सॉल्व्हर म्हणून दोन्ही कार्य करते. जर आपण ते आधीच तयार केलेल्या चक्रव्यूहावर चालविले आणि जेव्हा आपण ठरविलेल्या शेवटच्या बिंदूवर पोहोचता तेव्हा थांबा, स्टॅकमध्ये चक्रव्यूहाचे द्रावण असेल.

माझ्याकडे या साइटवर या अल्गोरिदमच्या दोन आवृत्त्या आहेत: या पृष्ठावर चक्रव्यूह तयार करण्यासाठी एक एलआयएफओ रांग आधारित आणि चक्रव्यूह सोडविण्यासाठी पुनरावृत्ती आधारित एक, इतर अल्गोरिदमद्वारे तयार केलेले चक्रव्यूह (अशा प्रकारे सोल्यूशन्ससह नकाशे तयार केले जातात). दोन वेगवेगळ्या आवृत्त्या असणे केवळ खेळांसाठी आहे कारण मी एक नर्ड आहे ज्याला ते मनोरंजक वाटते, एकतर दोन्हीसाठी कार्य करू शकले असते ;-)