时间戳

首页 > 解决方案 > 迷宫：寻找从起点到终点的最短路径

python - 迷宫：寻找从起点到终点的最短路径

问题描述

我目前正在学习一些 CS 基础知识（一周前开始），我偶然发现了这个挑战。迷宫是一个列表的列表，'#'指示一堵墙并' '指示一条开放的路径。就连续坐标而言，我应该找到从左下角到右上角的最短路径(col, row)。我必须在不导入任何东西的情况下创建一个函数。

例如：

maze = 
       [[' ', '#', ' ', '#', ' '],
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', ' ', ' ', ' ', ' '], 
        ['#', ' ', '#', ' ', ' '], 
        [' ', ' ', '#', '#', '#']]

首先我得到起点坐标(0, 9)和终点坐标(4, 0)。然后我需要找到最短路径。预期的结果是：[(0, 9), (1, 9), (1, 8), (1, 7), (2, 7), (3, 7), (4, 7), (4, 6), (4, 5), (4, 4), (4, 3), (4, 2), (4, 1), (4, 0)].

这是我的代码：

def grid(maze):
    ''' Maze Properties'''
    num_rows = len(maze)
    num_cols = len(maze[0])
    end_pt = (num_cols - 1, 0)
    start_pt = (0, num_rows - 1)
    print(start_pt, end_pt)

    '''Recursive Function'''

    def find_shortest(maze, start_point, end_point, visited, shortest_path):
        '''BASE CASE'''
        if start_point == end_point:
            return shortest_path


        adj_points = []
        '''FIND ADJACENT POINTS'''
        current_row = start_point[1]
        current_col = start_point[0]

        #UP
        if current_row > 0:
            if maze[current_row - 1][current_col] == " ":
                adj_points.append((current_col, current_row - 1))

        #RIGHT
        if current_col < (len(maze[0])-1):
            if maze[current_row][current_col] == " ":
                adj_points.append((current_col + 1, current_row))
        #DOWN
        if current_row < (len(maze) - 1):
            if maze[current_row + 1][current_col] == " ":
                adj_points.append((current_col, current_row + 1))
        #LEFT
        if current_col > 0:
            if maze[current_row][current_col - 1] == " ":
                adj_points.append((current_col - 1, current_row))

        print(adj_points)
        if all(elem in visited for elem in adj_points):
            return

        '''LOOP THROUGH ADJACENT PTS'''
        for point in adj_points:
            if point not in visited:
                visited.append(point)
                shortest_path.append(point)
                return find_shortest(maze, point, end_point, visited, shortest_path)



    path = [start_pt]
    visited = [start_pt]
    shortest_path = find_shortest(maze, start_pt, end_pt, visited, path)
    return shortest_path

我相信问题是如果我走到了死胡同，它应该回到最后一个有选择的地方，我不知道该怎么做。

注意：我相信这是 DFS，但 BFS 解决方案也将受到赞赏。

标签： pythonalgorithmdepth-first-searchbreadth-first-searchmaze

解决方案

您的 DFS 方法返回该特定迷宫的最短路径，因为它碰巧首先选择正确的方向，但它不会找到其他一些迷宫的最短路径。例如，对于这个迷宫：

maze = [[' ', ' ', ' ', '#', ' '],
        [' ', '#', ' ', '#', ' '],
        [' ', ' ', ' ', ' ', ' ']]

请注意，您的代码在缺少#RIGHTa 的情况下存在错误+ 1，因此实际上您的代码找不到上述迷宫的路径。即使纠正了这个错误，它也会找到更长的路径，首先到达网格的左上角。

为了找到最短路径，最好选择 BFS，因为这样您就可以确定目标的第一次命中对应于最短路径。

下面是适应 BFS 的代码，无需进行不必要的更改。请注意，visited这里不是一个列表，而是一本字典，它不仅告诉您访问了某个广场，还告诉您您是从哪个其他广场来访问它的。

有了这条信息，您就可以构建路径。

另外，我选择在这里从头到尾开始搜索，因为这样您就可以按照正确的顺序重建路径（展开）。否则，您必须在返回之前反转路径。

def grid(maze):
    ''' Maze Properties'''
    num_rows = len(maze)
    num_cols = len(maze[0])
    end_pt = (num_cols - 1, 0)
    start_pt = (0, num_rows - 1)

    '''BFS'''
    visited = {end_pt: None}
    queue = [end_pt]
    while queue:
        current = queue.pop(0)
        if current == start_pt:
            shortest_path = []
            while current:
                shortest_path.append(current)
                current = visited[current]
            return shortest_path
        adj_points = []
        '''FIND ADJACENT POINTS'''
        current_col, current_row = current
        #UP
        if current_row > 0:
            if maze[current_row - 1][current_col] == " ":
                adj_points.append((current_col, current_row - 1))
        #RIGHT
        if current_col < (len(maze[0])-1):
            if maze[current_row][current_col + 1] == " ": ## There was an error here!
                adj_points.append((current_col + 1, current_row))
        #DOWN
        if current_row < (len(maze) - 1):
            if maze[current_row + 1][current_col] == " ":
                adj_points.append((current_col, current_row + 1))
        #LEFT
        if current_col > 0:
            if maze[current_row][current_col - 1] == " ":
                adj_points.append((current_col - 1, current_row))

        '''LOOP THROUGH ADJACENT PTS'''
        for point in adj_points:
            if point not in visited:
                visited[point] = current
                queue.append(point)

maze = [[' ', '#', ' ', '#', ' '],
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', ' ', ' ', ' ', ' '], 
        ['#', ' ', '#', ' ', ' '], 
        [' ', ' ', '#', '#', '#']]

print(grid(maze))

推荐阅读