day20 Python 实现的广度优先搜索实现迷宫算法
时间: 2023-11-29 07:15:22 浏览: 40
好的,我来回答你的问题。首先,广度优先搜索(BFS)是一种图搜索算法,可以用来解决一些问题,比如迷宫问题。在迷宫问题中,我们需要找到一条从起点到终点的最短路径。下面是用 Python 实现 BFS 解决迷宫问题的示例代码:
```python
from collections import deque
# 定义一个二维数组表示迷宫,0 表示可以走,1 表示障碍物
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0],
]
# 定义起点和终点
start = (0, 0)
end = (4, 4)
# 定义四个方向,上下左右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs(maze, start, end):
# 定义队列,初始时将起点加入队列
queue = deque([start])
# 定义 visited 集合,用于记录已经访问过的位置
visited = set([start])
while queue:
# 取出队列中的第一个节点
node = queue.popleft()
# 如果当前节点是终点,返回到达终点的最短距离
if node == end:
return distance[node[0]][node[1]]
# 对于当前节点,遍历它的四个方向
for direction in directions:
# 计算出下一个节点的坐标
next_node = (node[0] + direction[0], node[1] + direction[1])
# 如果下一个节点不越界且没有访问过,并且可以走(maze[next_node[0]][next_node[1]] == 0),将它加入队列和 visited 集合
if 0 <= next_node[0] < len(maze) and 0 <= next_node[1] < len(maze[0]) and next_node not in visited and maze[next_node[0]][next_node[1]] == 0:
queue.append(next_node)
visited.add(next_node)
# 如果没有找到到达终点的路径,返回 -1
return -1
# 计算每个位置到起点的最短距离
distance = [[float('inf') for _ in range(len(maze[0]))] for _ in range(len(maze))]
distance[start[0]][start[1]] = 0
bfs(maze, start, end)
```
在上面的代码中,我们首先定义了一个迷宫,然后定义了起点和终点。接着,我们定义了四个方向,上下左右。接下来,我们定义了 bfs 函数,用于实现广度优先搜索。在 bfs 函数中,我们首先定义了一个队列和 visited 集合,用于记录已经访问过的位置。然后,我们将起点加入队列和 visited 集合。接着,我们进行循环,取出队列中的第一个节点,遍历它的四个方向。如果下一个节点不越界且没有访问过,并且可以走,我们将它加入队列和 visited 集合。最后,如果没有找到到达终点的路径,返回 -1。
最后,我们计算每个位置到起点的最短距离,并调用 bfs 函数求解最短路径。