广度优先搜索优化

Question

我最近一直在编写一些介绍性的图论，并遇到了以下问题说明：

给定一个2D矩阵作为输入，表示一个迷宫(其中'E‘是矩阵的开始，' S’是结束)，找出从E到S的最短路径的长度，迷宫中的墙壁用'#‘表示，而可访问的空间用'.’表示。它也是一个给定的，矩阵的外部边缘被墙壁覆盖。如果不存在从E到S的路径，return -1。

由于图形没有加权，所以我尝试使用deque实现BFS算法。然而，当迷宫开始达到500×500左右时，执行时间达到10s，而当我试图提高到1000x1000时，情况显然要糟糕得多。

，这是我的代码：

from collections import deque

def shortest_path_1(maze):
    wall, clear, endchar, startchar = '#', '.', 'S', 'E'
    height = len(maze)
    width = len(maze[0])

    def find_start(grid):
        for y in range(1, height-1):
            for x in range(1, width-1):
                if grid[y][x] == startchar:
                    return tuple([x, y])

    start = find_start(maze)

    queue = deque([[start]])

    seen = {start}
    while queue:
        path = queue.popleft()
        x, y = path[-1]
        if maze[y][x] == endchar:
            return len(path)-1
        for (x2, y2) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
            if 0 < x2 < width-1 and 0 < y2 < height-1 and maze[y2][x2] != wall and (x2, y2) not in seen:
                queue.append(path + [(x2, y2)])
                seen.add((x2, y2))

    return -1

到目前为止，我在网站上找到了一些非常有用的答案，但目前的答案似乎没有给出我还没有实现的任何其他优化。

谢谢!

编辑:感谢这位可爱的人，他编辑了我的问题，使关键词流行起来:)。下面是一个可以运行算法的矩阵示例：

#####
#E#S#
#.#.#
#...#
#####

这应该返回值6。

EDIT2:修正了一些小错误。

Answer 1

正如注释中所建议的，您不必存储路径。试试这个：

from collections import deque

def shortest_path_1(maze):
    wall, clear, endchar, startchar = '#', '.', 'S', 'E'
    height = len(maze)
    width = len(maze[0])

    def find_start(grid):
        for y in range(1, height-1):
            for x in range(1, width-1):
                if grid[y][x] == startchar:
                    return (x, y, 0)

    start = find_start(maze)

    queue = deque([start])

    seen = set()
    while queue:
        x, y, d = queue.popleft()

        if not 0 <= x < width:
            continue
        if not 0 <= y < height:
            continue
        if maze[y][x] == wall:
            continue

        if maze[y][x] == endchar:
            return d

        if (x, y) in seen:
            continue
        seen.add((x, y))

        queue.append((x+1, y, d+1))
        queue.append((x-1, y, d+1))
        queue.append((x, y+1, d+1))
        queue.append((x, y-1, d+1))

    return -1

maze = [x for x in """
#####
#E#S#
#.#.#
#...#
#####
""".split('\n') if x]

print shortest_path_1(maze)