מחולל מבוך רקורסיבי Backtracker

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

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

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

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

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

איך זה עובד

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

1. בחר תא התחלתי וסמן אותו כ"נצפה".
2. כל עוד ישנם תאים שלא ביקרו בהם: התבוננו בתאים השכנים שטרם ביקרו בהם. אם קיים לפחות שכן אחד שלא ביקר בהם: בחרו באופן אקראי אחד מהשכנים שלא ביקרו בהם. הסירו את הקיר בין התא הנוכחי לשכן שנבחר. זזו לשכן שנבחר וסמנו אותו כמי שביקרת בו. דחפו את התא הנוכחי אל הערימה. אם לא קיימים שכנים שלא ביקרו בהם: חזרו אחורה על ידי הוצאת התא האחרון מהערימה.
3. המשך בתהליך זה עד שהערימה ריקה.

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

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

קריאה נוספת

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

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