python - 如何使用 BFS 找到迷宫中的最短路径？

Question

我正在尝试找到解决迷宫的方法。我的老师说我必须使用 BFS 作为学习的一种方式。所以我自己编写了算法，但我不明白如何从中得到最短路径。我查看了其他人的代码，他们说回溯是做到这一点的方法。这种回溯是如何进行的以及回溯什么？

我会给出我的代码只是因为我喜欢一些反馈，也许我犯了一些错误:

def main(self, r, c):
    running = True
    self.queue.append((r, c))
    while running:
        if len(self.queue) > 0:  
            self.current = self.queue[0]
            if self.maze[self.current[0] - 1][self.current[1]] == ' ' and not (self.current[0] - 1, self.current[1])\
                    in self.visited and not (self.current[0] - 1, self.current[1]) in self.queue:
                self.queue.append((self.current[0] - 1, self.current[1]))
            elif self.maze[self.current[0] - 1][self.current[1]] == 'G':
                return self.path

            if self.maze[self.current[0]][self.current[1] + 1] == ' ' and not (self.current[0], self.current[1] + 1) in self.visited\
                    and not (self.current[0], self.current[1] + 1) in self.queue:
                self.queue.append((self.current[0], self.current[1] + 1))
            elif self.maze[self.current[0]][self.current[1] + 1] == 'G':
                return self.path

            if self.maze[self.current[0] + 1][self.current[1]] == ' ' and not (self.current[0] + 1, self.current[1]) in self.visited\
                    and not (self.current[0] + 1, self.current[1]) in self.queue:
                self.queue.append((self.current[0] + 1, self.current[1]))
            elif self.maze[self.current[0] + 1][self.current[1]] == 'G':
                return self.path

            if self.maze[self.current[0]][self.current[1] - 1] == ' ' and not (self.current[0], self.current[1] - 1) in self.visited\
                    and not (self.current[0], self.current[1] - 1) in self.queue:
                self.queue.append((self.current[0], self.current[1] - 1))
            elif self.maze[self.current[0]][self.current[1] - 1] == 'G':
                return self.path

            self.visited.append((self.current[0], self.current[1]))
            del self.queue[0]
            self.path.append(self.queue[0])

作为迷宫，我使用这样的东西:

############
# S        #
##### ######
#          #
######## ###
#          #
## ##### ###
#         G#
############

存储在矩阵中

我最终想要的只是列表中的最短路径作为输出。

Answer 1

由于这是一个编码作业，我将把代码留给您，并在这里简单地解释一下一般算法。

您有一个 n by m 网格。我假设这是提供给您的。您可以将其存储在二维数组中。

第 1 步)创建一个与网格大小相同的新二维数组，并使用无效坐标填充每个条目(由您决定，可以使用 None 或其他可用于指示的值尚未发现到达该坐标的路径)。我将把这个二维数组称为路径矩阵，将迷宫称为网格。

第 2 步)将起始坐标入队并更新该位置的路径矩阵(例如，如果坐标 (1,1) 是起始位置，则更新矩阵[1,1])。

步骤 3) 如果不在最终坐标，则将元素从队列中出列。对于出队坐标的每个可能方向，检查其是否有效(没有墙壁且矩阵中尚不存在该坐标)，并将所有有效坐标入队。

第 4 步)重复第 3 步。

如果有一条到达最终坐标的路径，您不仅可以使用此算法找到它，而且它也将是一条最短路径。要回溯，请检查最终坐标位置处的矩阵。这应该会引导您到达另一个坐标。继续此过程并回溯，直到到达起始坐标。如果您存储此回溯坐标列表，那么您将拥有一条反向路径。