זוהי שיטה טריוויאלית שיכולה להיות מיושמת על ידי רובוט מאוד לא מפותח או לחלופין על ידי עכבר. באלגוריתם זה, על מבצע האלגוריתם להמשיך בקו ישר עד שהוא מגיע לצומת, ואז להחליט החלטה אקראית לאן לפנות. על אף ששיטה כזו תביא תמיד את המשתמש בה לפתרון, אלגוריתם זה יכול להיות מאוד איטי ולא יעיל.
הליכה בעקבות הקיר.
הליכה בעקבות הקיר, השיטה הטובה ביותר לחצות מבוך, ידועה גם בשם "חוק יד שמאל" או "חוק יד ימין". אם המבוך הוא פשוט קשר, או במילים אחרות, כל קירות המבוך מחוברים ביניהם או לגבול המבוך החיצוני, אז אם חוצה המבוך ישאיר יד אחת על הקיר לאורך כל חציית המבוך, מובטח לו כי לא יאבד את דרכו ויגיע ליציאה אחרת אם יש כזו; אחרת, החוצה יחזור לכניסה ממנה הוא בה לאחר שעבר בכל מסדרון במבוך לפחות פעם אחת.
פרספקטיבה שונה להבנת הסיבה למה אלגוריתם זה עובד היא טופולגית. אם כל הקירות מחוברים זאת אומרת שהם ניתנים לסידור בצורת לולאה או מעגל. וכך יוצא שהליכה בעקבות הקיר היא בעצם הליכה מסביב למעגל מנקודת ההתחלה ועד הסוף. יתר על כן, אפשר לראות כי על ידי קיבוץ רכיבים מחוברים בקירות המבוך, הגבולות בין רכיבים אלו הם בדיוק הפתרונות, אפילו אם יש יותר מפתרון אחד. (ראו בתמונה בצד שמאל).
אם המבוך הוא לא פשוט קשר (כלומר, אם נקודת ההתחלה או הסיום נמצאות במרכז המבוך או שהמסלולים חוצים אחד מעל ומתחת לשני), שיטה זו לא תביא בהכרח לפתרון המבוך.
שיטת ההליכה בעקבות הקיר יכולה לעבוד במבוכים תלת-ממדיים ואף עם יותר ממדים אם אפשר להמיר את המעברים הרב ממדיים למישור דו ממדי באופן שיטתי. לדוגמה, אם במבוך תלת ממדי מעברים הפונים "למעלה" יכולים להיות מומרים במעברים בכיוון צפון מערב ומעברים הפונים "למטה" יכולים להיות מומרים בדרום מזרח בלוח דו ממדי, אזי ששיטה זו תוכל לעבוד. מכל מקום, שלא כמו במבוך דו ממדי, במבוך מסדר גבוה יותר נדרש לדעת מהו הכיוון הנוכחי אליו פונים, על מנת לקבוע איזה כיוון הוא הראשון מימין ואיזה משמאל.
אלגוריתם פלדג'.
מבוכים המפורקים לכמה אזורים או רכיבים יכולים להיפתר בשיטת ההליכה בעקבות הקיר, אם נקודות הכניסה והיציאה של המבוך נמצאות בקיר החיצוני של המבוך. אם פותר המבוך מתחיל לנווט בתוך המבוך, הוא עלול להיות באזור הנפרד מהיציאה, ובשימוש באלגוריתם ההליכה בעקבות הקיר הוא ימצא את עצמו חג במעגל סביב עצמו. אלגוריתם פלדג' (נקרא על שם ג'ון פלדג' מאקסטר) יכול לפתור בעיה זו.
אלגוריתם פלדג', שנועד לעקיפת מכשולים, דורש בחירה באופן שרירותי של כיוון אליו הפותר יפנה. כאשר מגיעים למכשול, יד אחת (לדוגמה יד ימין) נשמרת על המכשול לאורכו בזמן שסופרים את הזוויות שנפנו. כאשר הפותר ניצב שוב בכיוון המקורי אותו בחר, וסכום הזוויות אותו פנה שווה ל-0, הפותר עוזב את המכשול וממשיך לנוע בכיוונו המקורי.
היד יורדת מהקיר רק כאשר גם "סכום זוויות הפניות שנעשו" וגם "הכיוון הנוכחי אליו הוא פונה" שווים ל-0. כך נמנעים בשימוש באלגוריתם זה ממכשולים בצורת האות G לדוגמה. במקרה שהאלגוריתם פונה שמאלה בקיר הראשון, הוא צריך גם להסתובב 360° לאורך הקירות. אלגוריתם ששומר רק על "הכיוון הנוכחי" מוביל ללולאה אינסופית כאשר הוא עוזב את הקיר הימני-תחתון לפנייה לכיוון שמאל ונכנס עוד הפעם לאזור המעוקל בצד שמאל. אלגוריתם פלדג' לא עוזב את הקיר הימני עד ש"סכום זוויות הפניות שנעשו" שווה גם הוא ל-0 באותה הנקודה. הוא עוקב אחרי הקיר לאורך כל הדרך מחוץ לצורת ה-G עד שהוא עוזב בפנותו שמאלה בצד החיצוני של הקיר התחתון.
אלגוריתם זה מאפשר לאדם עם מצפן למצוא את דרכו החוצה ממבוך דו ממדי וסופי מכל נקודה מתוכו, ללא קשר למקומו של הפותר בתוך המבוך. מכל מקום, אלגוריתם זה לא יכול לעבוד בכיוון ההפוך, כלומר, הוא לא ימצא מנקודת התחלה הנמצאת על גבול המבוך נקודת סיום הנמצאת בתוכו.
אלגוריתם טרימו.
אלגוריתם טרימו, שהומצא בידי צ'ארלס פייר טרימו, היא שיטה יעילה למציאת הדרך החוצה ממבוך שדורשת ציור קווים על הרצפה על מנת לסמן מעבר, שעובדת בכל מבוך שיש לו מעברים מוגדרים היטב. כל מעבר יכול להיות באחד משלושה מצבים: או שלא עברו בו מעולם, או שעברו בו רק פעם אחת, או שעברו בו בדיוק פעמיים. כל פעם שכיוון נבחר הוא מסומן על ידי ציור קו על הרצפה (מצומת לצומת). בהתחלה, כיוון אקראי נבחר (אם יש יותר מאחד). בהגעה לצומת שהפותר עוד לא הגיע אליה (ללא סימונים קודמים), על הפותר לבחור כיוון אקראי ולסמנו. כאשר הפותר מגיע לצומת שסומנה כבר פעם אחת, עליו להסתובב וללכת אחורה (לא לפני שיסמן את המעבר פעם נוספת). אם זה לא המקרה, הפותר צריך לבחור את הכיוון עם הכי פחות סימונים (וכמו תמיד, לסמן גם אותו). כאשר הוא מגיע לבסוף לפתרון, מעברים שסומנו בדיוק פעם אחת מורים על הדרך הישירה להתחלה. אם אין יציאה, שיטה זו תיקח את המשתמש בה אל ההתחלה, שם כל המעברים מסומנים פעמיים. במקרה זה, כל מעבר שהפותר הלך בו יסומן פעמיים - פעם אחת בכל כיוון. תוצאת ההליכה הזו נקראת התחקות כפולה דו כיוונית.
בעיקרו של דבר, אלגוריתם זה הוא גרסה של אלגוריתם חיפוש לעומק.
מילוי דרך ללא מוצא.
מילוי דרך ללא מוצא הוא אלגוריתם לפתרון מבוכים בו ממלאים את כל הדרכים ללא מוצא, ומשאירים אך ורק את הדרך הנכונה לא מלאה. האלגוריתם יכול להיות שימושי בפתרון מבוך מצויר על נייר או עם תוכנת מחשב, אך לא יהיה שימושי לאדם הנמצא בתוך מבוך לא ידוע מאחר שהאלגוריתם הזה "מסתכל" על המבוך מלמעלה. השיטה היא:
אפשר לצפות בסרטון המדגים את פעולת אלגוריתם זה כאן: .
אלגוריתם זה לא יכול לקטוע בטעות את המעבר בין נקודת ההתחלה לנקודת הסיום מאחר שכל צעד באלגוריתם משמר את הטופולוגיה של המבוך. יתר על כן, התהליך לא יעצור "מוקדם מדי" משום שהתוצאה הסופית לא יכולה לכלול דרכים ללא מוצא. לכן, אם כל הדרכים ללא מוצא מולאו במבוך מושלם (מבוך ללא לולאות), אז רק הדרך שהיא הפתרון תישאר. אם האלגוריתם מבוצע במבוך קלוע חלקית (מבוך עם לולאות), אז כל הפתרונות האפשריים יישארו, אך לא יותר מכך.
אלגוריתם הדרך הקצרה ביותר.
כאשר למבוך יש כמה פתרונות אפשריים, הפותר ירצה למצוא את המעבר הקצר ביותר מנקודת ההתחלה לנקודת הסיום. אלגוריתם אפשרי מוצא את הדרך הקצרה ביותר על ידי ביצוע אלגוריתם חיפוש לרוחב, תוך כדי אלגוריתם חיפוש A*, משתמש בטכניקה היוריסטית. אלגוריתם החיפוש לרוחב משתמש בתור כדי להגיע לתאים בסדר של מרחק הולך גדל מההתחלה עד שמגיע לנקודת הסיום. כל תא שהגיעו אליו צריך לעקוב אחר המרחק שלו מנקודת ההתחלה או מהתא הסמוך אליו הקרוב יותר להתחלה שגרם לו להיכנס לתור. כאשר המיקום הסופי נמצא, הדרך הקצרה ביותר היא דרך התאים שנבחרו בסדר הפוך.
מבוכים עם דלתות לכיוון אחד.
מבוכים עם דלתות לכיוון אחד הם מאתגרים יותר, וקשה יותר למצוא להם את הפתרון, במיוחד כאשר רוב הדלתות מובילות לכיוון ההפוך מהיציאה. כאשר בוחרים דלתות באופן אקראי, יש לבחור מספר מעריכי של דלתות עד שמגיעים ליציאה. אפילו אם הפותר מצייר מפה תוך כדי חיפוש במבוך, עדיין יצטרך לעבור דרך מספר ריבועי של דלתות על מנת למצוא את היציאה. הטענה כי המקרה הגרוע ביותר הוא ריבועי מתוארת כאן: .
בראד קבאנה
בראד לואיס קבאנה (באנגלית: Brad Lewis Kavanagh; נולד ב-21 באוגוסט 1992) הוא שחקן, זמר ויוצר אנגלי, במקור מוויתהאן, קומבריה. ידוע בעיקר בתפקידו כפביאן ראטר, בסדרת הטלוויזיה של ניקלודיאון, בית אנוביס.
קריירת משחק.
בראד קבאנה התחיל לשחק כילד בקבוצת משחק מקומית בקומבריה עד שהוא הפך להצלחה עצומה כאשר הוא עשה את הופעת הבכורה שלו בווסט אנד במחזמר בילי אליוט - המחזמר בתפקיד החבר הטוב ביותר של בילי, מייקל, בגיל 11. הוא עדיין ביקר בבית מעת לעת, סייע בקבוצה מקומית לביקור חברים זקנים, וצפה בהצגות חדשות שהקבוצה המקומית יצרה.
קריירת טלוויזיה.
ב־2008, בראד קבאנה הציג את תחרות הכישרונות "My School Musical" בערוץ דיסני בבריטניה לצד המנצחת של השנה הקודמת, סמנתה דוראנס.
ב־2009, הוא הציג ב-Undercover Cou של ערוץ דיסני, והציג בMy Camp Rock. הוא הציג בהקרנת הבכורה של האחים ג'ונס 3D בבריטניה שכיסה את הבכורה בבריטניה מההופעה של האחים ג'ונס 3D בבוקר של שחרור הסרט. הוא היה שופט בHannah-Oke, תוכנית משחק מסוג X פקטור שבו המתמודדים ובני משפחותיהם שרים שירי האנה מונטנה. הוא גם הופיע בערוץ דיסני ארצות הברית "Pass The Plate".
באמצע 2010, קבאנה צילם את מופע הטלוויזיה החדש של ניקלודיאון House of Anubis, כאחת הדמויות המרכזיות, פביאן ראטר. בראד עבד עם חבריו למסך בכל זמן העלאת פרקים חדשים. מאז הוא המשיך לעבוד בשביל ניקלודיאון בעשיית פרויקטים שונים המקיפים את ההצלחה של הסדרה. הסדרה שודרה ל-2.9 מיליון בני אדם בארצות הברית בתאריך הקרנת הבכורה 1 בינואר 2011. בכורת עונה 2 הייתה ב-9 בינואר 2012 עד סביבות מרץ 2012. אחרי העונה השנייה הייתה הצלחה גדולה, קבאנה והשחקנים צולמו לעונה השלישית בקיץ 2012. הקרנת הבכורה הייתה במרס 2013 ובאפריל בבריטניה. ב-21 באפריל 2013, ניקלודיאון הודיעו על 90 דקות ספיישל של בית אנוביס, אבן הבוחן של רא, שקבאנה יככב בו כחלק מצוות השחקנים הראשי. צופי בית אנוביס עדיין מחכים להודעה על עונה 4.
מוזיקה.
קבאנה רשם ארבעה עשר שירים, המוקדמים שבהם: "כשהפעמון מצלצל" ו"הזמן הנכון", שניהם מוצגים בערוץ דיסני במרווחי זמן שווים במהלך היום.
הידעוני