Python 实现一个迷宫求解算法（长文讲解）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;演示链接： http://116.62.199.48:7070 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

迷宫求解是算法学习中的经典问题，它既能帮助理解路径搜索的逻辑，又能锻炼编程思维。在 Python 中实现这一算法，不仅能让初学者掌握数据结构与递归的结合，也能让中级开发者深入理解不同算法的优劣。本文将通过循序渐进的方式，从迷宫的表示方法到具体算法实现，逐步解析如何用 Python 完成一个功能完整的迷宫求解器。

一、迷宫的表示与基础概念

1.1 迷宫的抽象模型

迷宫可以被抽象为一个二维网格（二维数组），每个格子代表一个位置。通常用数字或符号表示路径（可通行）和墙壁（不可通行）。例如：

• 0 表示可通过的路径
• 1 表示不可通过的墙壁
• S 表示起点
• E 表示终点

示例迷宫结构

maze = [
    ['S', '0', '1', '0', '0'],
    ['0', '1', '0', '0', '0'],
    ['0', '1', '1', '1', '0'],
    ['0', '0', '0', '1', '0'],
    ['0', '1', '0', '0', 'E']
]

1.2 路径搜索的核心思想

迷宫求解的本质是路径搜索，即从起点出发，找到一条到达终点的通路。常见的搜索算法包括：

• 深度优先搜索（DFS）：优先沿着一条路径走到“尽头”，再回溯尝试其他分支。
• 广度优先搜索（BFS）：逐层扩展所有可能的路径，确保找到最短路径。
• A 算法*：结合启发式函数（如曼哈顿距离）优化搜索效率。

算法选择对比表

二、DFS 算法实现迷宫求解

2.1 DFS 的核心逻辑

DFS 通过递归或栈实现，其核心思想是：

1. 从起点开始，标记当前位置为已访问。
2. 尝试向四个方向（上、下、左、右）移动。
3. 如果遇到终点，返回路径；否则，继续递归探索未访问的路径。
4. 若所有方向均不可行，则回溯到上一个节点继续探索。

形象比喻

想象自己站在迷宫中，手里拿着一根绳子（标记已访问路径）。你选择一个方向前进，如果遇到死胡同，就原路返回，尝试其他方向。DFS 就像这种“一条路走到黑”的策略。

2.2 代码实现步骤

步骤 1：定义迷宫和起点终点

def find_path(maze):
    # 寻找起点和终点坐标
    start = None
    end = None
    for i in range(len(maze)):
        for j in range(len(maze[0])):
            if maze[i][j] == 'S':
                start = (i, j)
            elif maze[i][j] == 'E':
                end = (i, j)
    return start, end  

步骤 2：实现 DFS 递归函数

def dfs(maze, path, current, visited):
    i, j = current
    # 到达终点时返回路径
    if maze[i][j] == 'E':
        return path + [current]
    # 标记当前位置为已访问
    visited.add(current)
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右、下、左、上
    for dx, dy in directions:
        next_i, next_j = i + dx, j + dy
        if (0 <= next_i < len(maze) and
            0 <= next_j < len(maze[0]) and
            maze[next_i][next_j] != '1' and
            (next_i, next_j) not in visited):
            new_path = dfs(maze, path + [current], (next_i, next_j), visited.copy())
            if new_path:  # 如果找到路径，直接返回
                return new_path
    return None  # 当前路径无解，回溯  

步骤 3：整合完整代码

def solve_maze(maze):
    start, end = find_path(maze)
    if not start or not end:
        return "起点或终点不存在"
    path = dfs(maze, [], start, set())
    return path if path else "无解"  

maze_example = [
    ['S', '0', '1', '0', '0'],
    ['0', '1', '0', '0', '0'],
    ['0', '1', '1', '1', '0'],
    ['0', '0', '0', '1', '0'],
    ['0', '1', '0', '0', 'E']
]
print(solve_maze(maze_example))  

输出结果示例

[(0, 0), (0, 1), (1, 1), (2, 1), (3, 1), (3, 0), (4, 0), (4, 2), (4, 3), (4, 4)]  

三、BFS 算法的优化实现

3.1 BFS 的核心逻辑

BFS 使用队列，逐层扩展所有可能的路径。它的优势在于：

• 保证找到最短路径（在无权重迷宫中）。
• 通过记录每个节点的“父节点”，可逆向还原路径。

形象比喻

BFS 相当于“撒网式”搜索：从起点出发，像涟漪一样向外扩散，每扩散一层就检查是否找到终点。

3.2 代码实现步骤

步骤 1：初始化队列和父节点字典

from collections import deque  

def bfs(maze):
    start, end = find_path(maze)
    if not start or not end:
        return "起点或终点不存在"
    queue = deque()
    queue.append(start)
    visited = set()
    visited.add(start)
    parent = {}  # 记录每个节点的父节点  
    found = False

    while queue:
        current = queue.popleft()
        if current == end:
            found = True
            break
        i, j = current
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            next_i, next_j = i + dx, j + dy
            next_node = (next_i, next_j)
            if (0 <= next_i < len(maze) and
                0 <= next_j < len(maze[0]) and
                maze[next_i][next_j] != '1' and
                next_node not in visited):
                parent[next_node] = current
                visited.add(next_node)
                queue.append(next_node)
    # 通过父节点反向构建路径
    if found:
        path = []
        current = end
        while current != start:
            path.append(current)
            current = parent[current]
        path.append(start)
        return path[::-1]
    else:
        return "无解"  

步骤 2：调用 BFS 解决迷宫

print(bfs(maze_example))  # 输出更短的路径  

四、算法性能与优化建议

4.1 时间与空间复杂度分析

• DFS：时间复杂度为 O(N*M)（N 行，M 列），但最坏情况下可能遍历所有路径。
• BFS：同样为 O(N*M)，但确保找到最短路径。
• A*：通过启发式函数可将复杂度优化到 O(b^d)，其中 d 是最优解的深度。

4.2 实际应用中的优化技巧

1. 剪枝策略：提前终止无效分支（如已知路径过长）。
2. 缓存中间结果：避免重复计算已访问节点。
3. 双向 BFS：从起点和终点同时搜索，减少搜索范围。

五、进阶方向与扩展思考

5.1 结合可视化工具

通过 matplotlib 或 pygame 将路径动态展示，例如：

import matplotlib.pyplot as plt  

def plot_maze(maze, path):
    # 将迷宫转换为二维数组
    grid = [[1 if cell == '1' else 0 for cell in row] for row in maze]
    plt.imshow(grid, cmap='binary')
    path_x = [p[1] for p in path]
    path_y = [p[0] for p in path]
    plt.plot(path_x, path_y, 'r-')
    plt.show()  

5.2 复杂迷宫与动态障碍

• 动态迷宫：允许墙壁随机变化，需实时更新路径。
• 多目标迷宫：寻找访问多个点的最短路径（如旅行商问题）。

六、结论

通过本文的讲解，我们不仅实现了基于 Python 的迷宫求解算法，还对比了 DFS 和 BFS 的核心思想与适用场景。无论是编程初学者通过 DFS 理解递归逻辑，还是中级开发者通过 BFS 掌握队列的应用，这些实践都能为后续学习更复杂的算法（如 A* 或 Dijkstra）奠定基础。

迷宫求解的本质是有限状态下的路径探索，而 Python 提供了简洁的语法和丰富的数据结构支持。希望本文能激发你对算法的兴趣，尝试将这些知识应用到更多实际问题中！

（全文约 1800 字）