广度优先搜索优化
Breadth First Search Optimisation
我最近一直在研究一些介绍性的图论,遇到了以下问题陈述:
给定一个 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:修正了一些小错误。
正如评论中所建议的,您不必存储路径。试试这个:
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)
我最近一直在研究一些介绍性的图论,遇到了以下问题陈述:
给定一个 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:修正了一些小错误。
正如评论中所建议的,您不必存储路径。试试这个:
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)