אלגוריתמים לפתרון מבוכים

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

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

אלגוריתם העכבר האקראי

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

הליכה בעקבות הקיר

חציית מבוך בעזרת חוק יד ימין

מבוך עם שני פתרונות

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

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

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

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

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

אלגוריתם פלדג'

רובוט במבוך עץ

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

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

היד יורדת מהקיר רק כאשר גם "סכום זוויות הפניות שנעשו" וגם "הכיוון הנוכחי אליו הוא פונה" שווים ל-0. כך נמנעים בשימוש באלגוריתם זה ממכשולים בצורת האות G לדוגמה. במקרה שהאלגוריתם פונה שמאלה בקיר הראשון, הוא צריך גם להסתובב 360° לאורך הקירות. אלגוריתם ששומר רק על "הכיוון הנוכחי" מוביל ללולאה אינסופית כאשר הוא עוזב את הקיר הימני-תחתון לפנייה לכיוון שמאל ונכנס עוד הפעם לאזור המעוקל בצד שמאל. אלגוריתם פלדג' לא עוזב את הקיר הימני עד ש"סכום זוויות הפניות שנעשו" שווה גם הוא ל-0 באותה הנקודה. הוא עוקב אחרי הקיר לאורך כל הדרך מחוץ לצורת ה-G עד שהוא עוזב בפנותו שמאלה בצד החיצוני של הקיר התחתון.

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

אלגוריתם טרימו

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

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

מילוי דרך ללא מוצא

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

• למצוא את כל מבוי סתום במבוך.
• למלא או לסמן את הדרך מכל מבוי סתום ועד לצומת הראשונה.

אפשר לצפות בסרטון המדגים את פעולת אלגוריתם זה כאן: [1][2].

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

אלגוריתם הדרך הקצרה ביותר

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

מבוכים עם דלתות לכיוון אחד

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

ראו גם

• מבוך
• אלגוריתמים לייצור מבוכים
• פרק של משפחת סימפסון בו ליסה משתמשת באלגוריתם טרימו

קישורים חיצוניים

• Think Labyrinth: Maze algorithms (details on these and other maze solving algorithms)
• MazeBlog: Solving mazes using image analysis
• Maze generation and solving Java applet
• Video: Maze solving simulation, סרטון באתר יוטיוב