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

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

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

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

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

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

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

كيف تعمل خوارزمية كروسكال لإنشاء المتاهة

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

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

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

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

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

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

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

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

نظرًا لأن خوارزمية كروسكال تعتمد على دمج المجموعات، فيمكن تحسينها باستخدام خوارزمية Union-Find، والتي توفر طريقة فعّالة لتتبع الخلايا المتصلة أثناء إنشاء المتاهة. يمكنك الاطلاع على تنفيذي لخوارزمية Union-Find بلغة PHP هنا: مجموعة منفصلة (خوارزمية البحث عن الاتحاد) في PHP