广度优先搜索优化

Question

我最近一直在研究一些介绍性的图论，遇到了以下问题陈述：

给定一个 2D 矩阵 作为输入，表示一个迷宫（其中 'E' 是矩阵的开始，'S'为终点），求E到S的最短路径长度。迷宫中的墙用'#'表示，同时可以访问空格用“.”表示。矩阵的外边缘被墙覆盖也是一个假设。如果不存在从 E 到 S 的路径，return -1.

由于图表没有加权，我尝试使用双端队列实现 BFS 算法。然而，当迷宫开始在 500x500 附近时，执行时间达到 10 秒，而当我尝试上升到 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

到目前为止，我在网站上找到了一些非常有用的答案，但是 none 当前的答案似乎提供了我尚未实现的任何其他优化...

谢谢！

编辑：感谢可爱的人编辑了我的问题，使关键词流行:)。这是您可以运行算法的矩阵示例：

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

这应该return值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)

广度优先搜索优化

Breadth First Search Optimisation

python

performance

optimization

graph-theory

breadth-first-search