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

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

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

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

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

क्रुस्कलको एल्गोरिथ्म अमेरिकी गणितज्ञ, तथ्याङ्कशास्त्री र कम्प्युटर वैज्ञानिक जोसेफ बर्नार्ड क्रुस्कल जुनियरले सिर्जना गरेका थिए। उनले पहिलो पटक १९५६ मा आफ्नो पेपर "अन द सर्टेस्ट स्प्यानिङ सबट्री अफ अ ग्राफ एन्ड द ट्राभलिङ सेल्सम्यान प्रबलम" मा एल्गोरिथ्मको वर्णन गरेका थिए।

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

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

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

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

चरण २: भित्ताहरू क्रमबद्ध गर्नुहोस्

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

चरण ३: पर्खालहरू प्रशोधन गर्नुहोस्

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

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

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

क्रुस्कलको एल्गोरिथ्म सेटहरू मर्ज गर्ने कुरामा निर्भर हुने भएकोले, यसलाई युनियन-फाइन्ड एल्गोरिथ्म प्रयोग गरेर अप्टिमाइज गर्न सकिन्छ, जसले भूलभुलैया उत्पादनको समयमा जडान गरिएका सेलहरू ट्र्याक गर्ने प्रभावकारी तरिका प्रदान गर्दछ। तपाईंले युनियन-फाइन्ड एल्गोरिथ्मको मेरो PHP कार्यान्वयन यहाँ हेर्न सक्नुहुन्छ: लिङ्क

थप पढाइ

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

• हन्ट र किल भूलभुलैया जेनरेटर
• एलरको एल्गोरिदम भूलभुलैया जेनरेटर
• बढ्दो रूख एल्गोरिदम भूलभुलैया जेनरेटर