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