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

क्रुस्कलको एल्गोरिदम एक न्यूनतम विस्तारित रूख एल्गोरिदम हो जुन भूलभुलैया उत्पादनको लागि अनुकूलित गर्न सकिन्छ। यो विशेष गरी सिद्ध भूलभुलैया सिर्जना गर्न प्रभावकारी छ। क्रुस्कलको एल्गोरिदमको विकल्प प्रिमको एल्गोरिदम हो, जुन न्यूनतम विस्तारित रूख एल्गोरिदम पनि हो, तर किनकि उनीहरूले समान भूलभुलैया उत्पन्न गर्छन् र क्रुस्कलको छिटो चल्छ, मैले प्राइमको कार्यान्वयन गर्न चिन्ता गरेको छैन।

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

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

क्रुस्कलको एल्गोरिदमको बारेमा

क्रुस्कलको एल्गोरिदम एक अमेरिकी गणितज्ञ, सांख्यिकीविद् र कम्प्युटर वैज्ञानिक जोसेफ बर्नार्ड क्रुस्कल, जुनियरले सिर्जना गरेका थिए। उनले पहिलो पटक 1956 मा एल्गोरिदमको वर्णन आफ्नो पेपरमा गरे "ग्राफको सबैभन्दा छोटो स्पैनिंग सबट्री र यात्रा सेल्सम्यान समस्यामा।

एल्गोरिथ्म ग्राफको न्यूनतम स्प्यानिंग ट्री (एमएसटी) पत्ता लगाउन डिजाइन गरिएको छ, यो सुनिश्चित गर्दछ कि सबै शीर्षहरू न्यूनतम सम्भव कुल किनारा वजनसँग जोडिएको छ जबकि चक्रबाट जोगिन्छ।

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

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

• भूलभुलैया मा प्रत्येक सेल एक अलग सेट (एक अद्वितीय घटक) को रूप मा व्यवहार गर्नुहोस्।
• सम्भावित किनाराहरूको रूपमा आसन्न कक्षहरू बीचको सबै भित्ताहरू सूचीबद्ध गर्नुहोस्।

चरण २: पर्खालहरू क्रमबद्ध गर्नुहोस्

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

चरण 3: प्रक्रिया पर्खालहरू

• घुमाउरो भित्ताहरू मार्फत पुनरावृत्ति गर्नुहोस्।
• यदि भित्ताद्वारा विभाजित दुई कक्षहरू विभिन्न सेटहरूसँग सम्बन्धित छन् (जस्तै, तिनीहरू अझै भूलभुलैयामा जडान गरिएका छैनन्), भित्ता हटाउनुहोस् र सेटहरू मर्ज गर्नुहोस्।
• यदि तिनीहरू पहिले नै एउटै सेटमा छन् भने, भित्ता छोड्नुहोस् (चक्रबाट बच्न)।

चरण 4: पूरा नभएसम्म जारी राख्नुहोस्

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

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