مولد متاهة خوارزمية كروسكال

خوارزمية كروسكال هي خوارزمية شجرة ممتدة دنيا، ويمكن تكييفها لتوليد المتاهات. وهي فعالة بشكل خاص في إنشاء متاهات مثالية. يُعدّ بريم بديلاً لخوارزمية كروسكال، وهو أيضاً خوارزمية شجرة ممتدة دنيا، ولكن بما أنهما تُولّدان متاهات متطابقة، ولأن خوارزمية كروسكال أسرع، لم أُكلّف نفسي عناء تطبيق خوارزمية بريم.

المتاهة المثالية هي المتاهة التي يوجد بها مسار واحد فقط من أي نقطة في المتاهة إلى أي نقطة أخرى. وهذا يعني أنه لا يمكنك أن تنتهي إلى الدوران في دوائر، ولكنك ستواجه غالبًا نهايات مسدودة، مما يضطرك إلى الالتفاف والعودة.

تتضمن خرائط المتاهة التي تم إنشاؤها هنا إصدارًا افتراضيًا بدون أي مواضع بداية ونهاية، لذا يمكنك تحديدها بنفسك: سيكون هناك حل من أي نقطة في المتاهة إلى أي نقطة أخرى. إذا كنت تريد الإلهام، فيمكنك تمكين موضع بداية ونهاية مقترح - وحتى رؤية الحل بين الاثنين.

حول خوارزمية كروسكال

ابتكر خوارزمية كروسكال جوزيف برنارد كروسكال الابن، وهو عالم رياضيات وإحصاء وعلوم حاسوب أمريكي. وقد وصف الخوارزمية لأول مرة عام 1956 في بحثه بعنوان "حول أقصر شجرة فرعية ممتدة للرسم البياني ومسألة البائع المتجول".

تم تصميم الخوارزمية لإيجاد الشجرة الممتدة الدنيا (MST) للرسم البياني، مما يضمن أن جميع الرؤوس متصلة بأقل وزن إجمالي ممكن للحواف مع تجنب الدورات.

كيف تعمل خوارزمية كروسكال في توليد المتاهات

الخطوة 1: التهيئة

• تعامل مع كل خلية في المتاهة كمجموعة منفصلة (مكون فريد).
• أدرج جميع الجدران بين الخلايا المتجاورة كحواف محتملة.

الخطوة الثانية: فرز الجدران

• قم بخلط أو ترتيب الجدران عشوائياً. إذا كنت ستطبقها كخوارزمية كروسكال حقيقية، فقم بترتيب الجدران بترتيب عشوائي (لأن توليد المتاهة لا يتطلب أوزاناً).

الخطوة 3: جدران العملية

• قم بالتكرار عبر الجدران المختلطة.
• إذا كانت الخليتان المفصولتان بالجدار تنتميان إلى مجموعات مختلفة (أي أنهما لم تتصلا بعد في المتاهة)، فقم بإزالة الجدار وادمج المجموعات.
• إذا كانوا موجودين بالفعل في نفس المجموعة، فتجاوز الجدار (لتجنب الحلقات).

الخطوة الرابعة: استمر حتى الانتهاء

• كرر هذه العملية حتى يتم توصيل جميع الخلايا، لتشكيل شجرة ممتدة واحدة.
• في النهاية، تتصل كل خلية بالخلايا الأخرى دون حلقات أو أقسام معزولة.

بما أن خوارزمية كروسكال تعتمد على دمج المجموعات، يمكن تحسينها باستخدام خوارزمية الاتحاد والبحث، التي توفر طريقة فعالة لتتبع الخلايا المتصلة أثناء إنشاء المتاهة. يمكنك الاطلاع على تطبيق PHP الخاص بي لخوارزمية الاتحاد والبحث هنا: الرابط

قراءات إضافية

إذا أعجبك هذا المنشور، فقد تعجبك أيضًا هذه الاقتراحات:

• مولد متاهة الصيد والقتل
• مولد متاهة خوارزمية ويلسون
• مولد المتاهة لخوارزمية إلير