מציאת מסלול במבוך

נתונה מטריצה שמתארת מבוך.

תאים שבהם מופיע 0 הם אזורים פתוחים ותאים שבהם מופיע 1 הם קירות. שני תאים במטריצה מסומנים כ”כניסה” ו”יציאה”.

המשימה היא למצוא מסלול המוביל מהכניסה ליציאה אם קיים כזה.

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

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

נתחיל מדוגמא.
למשל המבוך הזה –

הייצוג של המבוך כמטריצה יהיה –

והמסלול שארצה לקבל במקרה כזה הוא –

(0,1),(1,1),(2,1),(2,2),(3,2)

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

מה האלגוריתם יעשה?

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

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

הכל טוב ויפה, אבל עכשיו, מה קורה אם המיקום שאליו האלגוריתם הגיע מוקף בקירות?

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

נשמע לא רע, אני אנסה לכתוב את זה בקוד.

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

def find_path_to_exit_in_maze(start_cell):
    path = [start_cell]
    while len(path) > 0:
        current_cell = path[-1]
        current_cell.visited = True

        adjacent_cell = get_available_adjacent_cell(current_cell)
        if adjacent_cell is None:
            path.pop()
        else:
            path.append(adjacent_cell)
            if adjacent_cell.is_exit:
                return path

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

start_cell=(0,1, visited=False)
path=[]
path=[(0,1)]
current_cell=(0,1, visited=True)
adjacent_cell = (1,1, visited=False) 
path=[(0,1),(1,1)]
current_cell=(1,1, visited=True)
adjacent_cell=(1,2, visited=False)
path=[(0,1),(1,1),(1,2)]
current_cell=(1,2, visited=True)
adjacent_cell = None
path=[(0,1),(1,1)]
current_cell=(1,1, visited=True)
adjacent_cell=(2,1)
.
.
.
.
current_cell=(3,2, visited=True)
adjacent_cell = (4,2)
path=[(0,1),(1,1),(2,1),(3,1),(3,2),(4,2)]
return (0,1),(1,1),(2,1),(3,1),(3,2),(4,2)

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

 A =  1 ⎐ 1 1
      1 0 0 1
      1 1 1 1
      1 0 0 1
      1 1 ⎏ 1  

start_cell=(0,1, visited=False)
path=[]
path=[(0,1)]
current_cell=(0,1, visited=True)
adjacent_cell = (1,1, visited=False) 
path=[(0,1),(1,1)]
current_cell=(1,1, visited=True)
adjacent_cell=(1,2, visited=False)
path=[(0,1),(1,1),(1,2)]
current_cell=(1,2, visited=True)
adjacent_cell = None
path=[(0,1),(1,1)]
current_cell=(1,1, visited=True)
adjacent_cell = None
path=[(0,1)]
current_cell=(0,1, visited=True)
adjacent_cell = None
path=[]

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

def find_path_to_exit_in_maze(start_cell):
    path = [start_cell]
    while len(path) > 0:
        current_cell = path[-1]
        current_cell.visited = True

        adjacent_cell = get_available_adjacent_cell(current_cell)
        if adjacent_cell is None:
            path.pop()
        else:
            path.append(adjacent_cell)
            if adjacent_cell.is_exit:
                return path

אחלה, יש אלגוריתם עובד, נהדר!

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

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

def get_available_adjacent_cell(cell):
    for (i, j) in [(cell.i - 1, cell.j), (cell.i, cell.j - 1), (cell.i + 1, cell.j), (cell.i, cell.j + 1)]:
        if 0 <= i < self.rows and 0 <= j < self.columns:
            adj = self.get_cell(i,j)
            if adj.visited or adj.is_wall:
                continue
            else:
                return adj

    return None

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

cell = (0,1)
(i,j) = (-1,1)
i>=0 → False
(i,j) = (0,0)
i >= 0 and i < self.rows and j >= 0 and j < self.columns → True
adj = (0,0, visited = False, is_wall = True)
adj.visited or adj.is_wall → True
(i,j) = (1,1)
i >= 0 and i < self.rows and j >= 0 and j < self.columns → True
adj = (1,1, visited = False, is_wall = False)
return adj

עובד מצוין.

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

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

מוזמנים לצפות בקוד בגיט – https://github.com/mgershovitz/maya_solves/blob/master/maze.py