מחולל מבוך האלגוריתם של קרוסקל

האלגוריתם של Kruskal הוא אלגוריתם עץ מינימלי שניתן להתאים ליצירת מבוך. זה יעיל במיוחד ליצירת מבוכים מושלמים. חלופה לאלגוריתם של Kruskal היא האלגוריתם של Prim, שהוא גם אלגוריתם עץ מינימלי, אבל מכיוון שהם מייצרים מבוכים זהים וה-Krusskal של Kruskal פועל מהר יותר, לא טרחתי ליישם את Prim.

מבוך מושלם הוא מבוך שבו יש בדיוק נתיב אחד מכל נקודה במבוך לכל נקודה אחרת. זה אומר שאתה לא יכול בסופו של דבר להסתובב במעגלים, אבל לעתים קרובות תתקל במבוי סתום, מה שיאלץ אותך להסתובב ולחזור.

מפות המבוך שנוצרות כאן כוללות גרסת ברירת מחדל ללא כל עמדות התחלה וסיום, כך שתוכלו להחליט על אלו בעצמכם: יהיה פתרון מכל נקודה במבוך לכל נקודה אחרת. אם תרצו השראה, תוכלו לאפשר עמדת התחלה וסיום מוצעת - ואפילו לראות את הפתרון בין השניים.

על האלגוריתם של קרוסקל

האלגוריתם של Kruskal נוצר על ידי ג'וזף ברנרד Kruskal, Jr., מתמטיקאי, סטטיסטיקאי ומדען מחשבים אמריקאי. הוא תיאר את האלגוריתם לראשונה בשנת 1956 במאמרו "על תת-העץ הקצר ביותר של גרף ובעיית המכירות הנודדות".

האלגוריתם נועד למצוא את עץ המתח המינימלי (MST) של גרף, ומבטיח שכל הקודקודים מחוברים למשקל הקצה המינימלי האפשרי תוך הימנעות ממחזוריות.

כיצד האלגוריתם של קרוסקל עובד עבור דור המבוך

שלב 1: אתחול

• התייחסו לכל תא במבוך כסט נפרד (רכיב ייחודי).
• רשום את כל הקירות בין תאים סמוכים כקצוות פוטנציאליים.

שלב 2: מיון קירות

• ערבב או סדר אקראי את הקירות. אם מיישמים אותו כאלגוריתם אמיתי של Kruskal, מיון קירות בסדר אקראי (מכיוון שיצירת מבוך אינה דורשת משקלים).

שלב 3: עיבוד קירות

• חזרו דרך הקירות המעורבבים.
• אם שני התאים המחולקים על ידי הקיר שייכים לקבוצות שונות (כלומר, הם עדיין לא מחוברים במבוך), הסר את הקיר ומאחד את הקבוצות.
• אם הם כבר באותו סט, דלג על הקיר (כדי למנוע מחזוריות).

שלב 4: המשך עד להשלמתו

• חזור על תהליך זה עד שכל התאים מחוברים, ויוצרים עץ פורש יחיד.
• בסוף, כל תא מחובר לאחרות ללא לולאות או קטעים מבודדים.

מכיוון שהאלגוריתם של Kruskal מסתמך על ערכות מיזוג, ניתן לייעל אותו על ידי שימוש באלגוריתם Union-Find, המספק דרך יעילה לעקוב אחר תאים מחוברים במהלך יצירת מבוך. אתה יכול לראות את יישום ה-PHP שלי של אלגוריתם Union-Find כאן: Disjoint Set (Union-Find Algorithm) ב-PHP