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

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

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

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

אודות אלגוריתם קרוסקל

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

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

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

שלב 1: אתחול

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

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

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

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

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

שלב 4: המשך עד לסיום

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

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

קריאה נוספת

אם נהניתם מהפוסט הזה, אולי תאהבו גם את ההצעות הבאות:

• מצוד והרוג מחולל מבוך
• מחולל מבוך האלגוריתם של ווילסון
• מחולל מבוך רקורסיבי Backtracker