क्रुस्कलचा अल्गोरिथम मेझ जनरेटर

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

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

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

क्रुस्कलच्या अल्गोरिथम बद्दल

क्रुस्कलचा अल्गोरिथम अमेरिकन गणितज्ञ, सांख्यिकीशास्त्रज्ञ आणि संगणक शास्त्रज्ञ जोसेफ बर्नार्ड क्रुस्कल ज्युनियर यांनी तयार केला होता. त्यांनी प्रथम १९५६ मध्ये त्यांच्या "ऑन द शॉर्टेस्ट स्पॅनिंग सबट्री ऑफ अ ग्राफ अँड द ट्रॅव्हलिंग सेल्समन प्रॉब्लेम" या पेपरमध्ये अल्गोरिथमचे वर्णन केले होते.

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

भूलभुलैया निर्मितीसाठी क्रुस्कलचे अल्गोरिथम कसे कार्य करते

पायरी १: सुरू करा

• चक्रव्यूहातील प्रत्येक पेशीला एक वेगळा संच (एक अद्वितीय घटक) म्हणून हाताळा.
• लगतच्या पेशींमधील सर्व भिंतींना संभाव्य कडा म्हणून सूचीबद्ध करा.

पायरी २: भिंती क्रमवारी लावा

• भिंती हलवा किंवा यादृच्छिकपणे क्रमवारी लावा. जर ते खऱ्या क्रुस्कलच्या अल्गोरिथम म्हणून अंमलात आणत असाल, तर भिंती यादृच्छिक क्रमाने लावा (कारण भूलभुलैया निर्मितीसाठी वजनांची आवश्यकता नसते).

पायरी ३: भिंतींवर प्रक्रिया करा

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

पायरी ४: पूर्ण होईपर्यंत सुरू ठेवा

• सर्व पेशी एकमेकांशी जोडल्या जाईपर्यंत, एकच स्पॅनिंग ट्री तयार होईपर्यंत ही प्रक्रिया पुन्हा करा.
• शेवटी, प्रत्येक सेल लूप किंवा वेगळ्या विभागांशिवाय इतरांशी जोडलेला असतो.

क्रुस्कलचा अल्गोरिथम संचांच्या विलीनीकरणावर अवलंबून असल्याने, तो युनियन-फाइंड अल्गोरिथम वापरून ऑप्टिमाइझ केला जाऊ शकतो, जो मेझ जनरेशन दरम्यान कनेक्टेड सेल्स ट्रॅक करण्याचा एक प्रभावी मार्ग प्रदान करतो. तुम्ही युनियन-फाइंड अल्गोरिथमचे माझे PHP अंमलबजावणी येथे पाहू शकता: पीएचपीमध्ये विसंगत संच (युनियन-फाइंड अल्गोरिदम)