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

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

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

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

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

लूप-मेटाइएको अनियमित भित्ता प्रयोग गरेर एकसमान स्प्यानिङ रूखहरू उत्पन्न गर्ने विल्सनको एल्गोरिथ्म डेभिड ब्रुस विल्सनद्वारा सिर्जना गरिएको थियो।

विल्सनले मूल रूपमा १९९६ मा सम्भाव्यता सिद्धान्तमा अनियमित स्प्यानिङ रूखहरू र मार्कोभ चेनहरूको अनुसन्धान गर्दा यो एल्गोरिथ्म प्रस्तुत गरेका थिए। यद्यपि उनको काम मुख्यतया गणित र सांख्यिकीय भौतिकीमा थियो, तर पूर्ण रूपमा एकरूप भूलभुलैयाहरू उत्पादन गर्ने क्षमताको कारणले गर्दा भूलभुलैया उत्पादनको लागि एल्गोरिथ्मलाई व्यापक रूपमा अपनाइएको छ।

भूलभुलैया उत्पादनको लागि विल्सनको एल्गोरिथ्मले कसरी काम गर्छ

विल्सनको एल्गोरिथ्मले अनियमित पदयात्रा प्रयोग गरेर भ्रमण नगरिएका कक्षहरूबाट पुनरावृत्ति रूपमा बाटोहरू खोपेर अन्तिम भूलभुलैया कुनै पनि लूप बिना पूर्ण रूपमा जडान भएको सुनिश्चित गर्दछ।

चरण १: सुरु गर्नुहोस्

• भित्ताहरूले भरिएको ग्रिडबाट सुरु गर्नुहोस्।
• सबै सम्भावित मार्ग कक्षहरूको सूची परिभाषित गर्नुहोस्।

चरण २: एउटा अनियमित सुरुवात कक्ष छनौट गर्नुहोस्

• कुनै पनि अनियमित कक्ष छान्नुहोस् र भ्रमण गरिएको रूपमा चिन्ह लगाउनुहोस्। यसले पुस्ताको समयमा भूलभुलैयाको सुरुवात बिन्दुको रूपमा काम गर्दछ।

चरण ३: लूप-इरेजिङको साथ अनियमित हिँडाइ

• भ्रमण नगरिएको कक्ष छान्नुहोस् र अनियमित हिँडाइ सुरु गर्नुहोस् (अनियमित दिशामा सर्दै)।
• यदि पैदल यात्रा पहिले नै भ्रमण गरिएको कक्षमा पुग्यो भने, बाटोमा रहेका सबै लूपहरू मेटाउनुहोस्।
• एकपटक पैदल यात्रा भ्रमण गरिएको क्षेत्रमा जडान भएपछि, मार्गमा रहेका सबै कक्षहरूलाई भ्रमण गरिएको रूपमा चिन्ह लगाउनुहोस्।

चरण ४: सबै कक्षहरू भ्रमण नभएसम्म दोहोर्याउनुहोस्:

• प्रत्येक कोष भूलभुलैयाको भाग नभएसम्म भ्रमण नगरिएका कोषहरू चयन गर्न र अनियमित हिँडाइहरू गर्न जारी राख्नुहोस्।

थप पढाइ

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

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