אלגוריתמים לייצור מבוכים

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

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

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

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

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

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

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

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

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