### Python 实现迷宫路径算法 以下是关于如何使用 Python 编写迷宫路径算法的详细介绍，其中包括 Dijkstra 算法以及广度优先搜索 (BFS) 的应用。 #### 使用 BFS 寻找迷宫中的最短路径 广度优先搜索是一种适合解决无权图中两点间最短路径问题的经典算法。它通过逐层扩展节点来找到目标位置，因此非常适合用于迷宫寻路场景[^1]。 下面是一个简单的 BFS 实现示例： ```python from collections import deque def bfs_maze(maze, start, goal): rows, cols = len(maze), len(maze[0]) visited = [[False for _ in range(cols)] for _ in range(rows)] parent = [[None for _ in range(cols)] for _ in range(rows)] queue = deque() queue.append(start) visited[start[0]][start[1]] = True directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 右 下 左 上 while queue: current = queue.popleft() if current == goal: path = [] while current != start: path.append(current) current = parent[current[0]][current[1]] path.append(start) return list(reversed(path)) for direction in directions: neighbor = (current[0] + direction[0], current[1] + direction[1]) if ( 0 <= neighbor[0] < rows and 0 <= neighbor[1] < cols and not visited[neighbor[0]][neighbor[1]] and maze[neighbor[0]][neighbor[1]] == 0 ): queue.append(neighbor) visited[neighbor[0]][neighbor[1]] = True parent[neighbor[0]][neighbor[1]] = current return None ``` 此函数接受一个二维数组 `maze` 表示迷宫地图，其中 `0` 表示可通过的位置，而 `1` 则表示障碍物；参数 `start` 和 `goal` 是起点和终点坐标元组。返回的结果是从起点到终点的一条路径列表，如果找不到则返回 `None`。 #### 使用 Dijkstra 算法处理加权迷宫 当迷宫中有不同权重（例如移动成本）时，则可以采用 Dijkstra 算法计算带权最短路径。尽管在标准迷宫问题中通常不需要考虑权重差异，但在某些复杂情况下可能需要用到该方法。 下面是基于堆优化版的 Dijkstra 实现代码片段： ```python import heapq def dijkstra_maze(maze, weights, start, goal): rows, cols = len(maze), len(maze[0]) distances = {(i, j): float('inf') for i in range(rows) for j in range(cols)} distances[start] = 0 priority_queue = [] heapq.heappush(priority_queue, (distances[start], start)) came_from = {start: None} directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] while priority_queue: dist_to_current, current = heapq.heappop(priority_queue) if current == goal: break for d in directions: next_cell = (current[0]+d[0], current[1]+d[1]) if 0<=next_cell[0]<rows and 0<=next_cell[1]<cols \ and maze[next_cell[0]][next_cell[1]]==0: tentative_dist = dist_to_current + weights.get(next_cell, 1) if tentative_dist < distances[next_cell]: distances[next_cell] = tentative_dist came_from[next_cell] = current heapq.heappush(priority_queue,(tentative_dist,next_cell)) if goal not in came_from or distances[goal]==float('inf'): return [], [] reconstruct_path = [] node = goal while node is not None: reconstruct_path.insert(0,node) node = came_from[node] return reconstruct_path,distances[goal] ``` 这段程序实现了利用最小优先队列加速版本的迪杰斯特拉算法，适用于具有特定边权值的地图环境下的最优路线探索任务需求情境之中。