विल्सन अल्गोरिदम मेझ जनरेटर

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

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

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

विल्सनच्या अल्गोरिदमबद्दल

लूप-मिटलेल्या यादृच्छिक भिंतीचा वापर करून एकसमान पसरलेली झाडे तयार करण्याचा विल्सनचा अल्गोरिदम डेव्हिड ब्रूस विल्सन यांनी तयार केला होता.

विल्सन यांनी १९९६ मध्ये संभाव्यता सिद्धांतातील यादृच्छिक पसरलेल्या वृक्ष आणि मार्कोव्ह साखळींवर संशोधन करताना हा अल्गोरिदम सादर केला. त्यांचे काम प्रामुख्याने गणित आणि सांख्यिकी भौतिकशास्त्रात असले तरी पूर्णपणे एकसमान चक्रव्यूह तयार करण्याच्या क्षमतेमुळे अल्गोरिदम नंतर चक्रव्यूह निर्मितीसाठी मोठ्या प्रमाणात स्वीकारला गेला आहे.

विल्सनचा अल्गोरिदम चक्रव्यूह निर्मितीसाठी कसा कार्य करतो

विल्सनचा अल्गोरिदम हे सुनिश्चित करतो की यादृच्छिक चालण्याचा वापर करून न पाहिलेल्या पेशींमधून मार्ग कोरून अंतिम चक्रव्यूह कोणत्याही लूपशिवाय पूर्णपणे जोडला गेला आहे.

चरण 1: प्रारंभ करा

• भिंतींनी भरलेल्या ग्रीडपासून सुरुवात करा.
• सर्व संभाव्य मार्ग पेशींची यादी परिभाषित करा.

चरण 2: यादृच्छिक प्रारंभ सेल निवडा

• कोणताही यादृच्छिक सेल निवडा आणि भेट दिल्याप्रमाणे चिन्हांकित करा. हे पिढीदरम्यान चक्रव्यूहाचा प्रारंभ बिंदू म्हणून कार्य करते.

चरण 3: लूप-इरेझिंगसह रॅंडम वॉक

• न पाहिलेला सेल निवडा आणि यादृच्छिक चालणे (यादृच्छिक दिशेने चालणे) सुरू करा.
• जर चालणे आधीच भेट दिलेल्या सेलपर्यंत पोहोचले तर मार्गातील कोणतेही लूप पुसून टाका.
• एकदा वॉक भेट दिलेल्या क्षेत्राशी जोडला गेल्यानंतर, मार्गातील सर्व पेशींना भेट दिल्याप्रमाणे चिन्हांकित करा.

चरण 4: सर्व पेशींना भेट देईपर्यंत पुनरावृत्ती करा:

• प्रत्येक पेशी चक्रव्यूहाचा भाग होईपर्यंत न पाहिलेल्या पेशी निवडणे आणि यादृच्छिक चालणे सुरू ठेवा.