老鼠走迷宫 算法实验详解

游戏简介

老鼠走迷宫是计算机算法、人工智能入门最经典的仿真实验课题，核心模拟一只老鼠在带墙壁的二维网格迷宫里面，从起点出发，依靠搜索算法自主寻找通往终点出口的路径，这个实验最早源自心理学斯金纳迷宫实验，后来被大量编程教学、AI 课程拿来做案例，大家学习老鼠走迷宫，主要是因为它把抽象的搜索算法变成可视化场景，不用理解复杂数学公式，就能直观看到算法如何试探、回溯、寻找通路，常见实现包含深度优先搜索 DFS、广度优先搜索 BFS、A 星算法、贪心算法，不同算法在老鼠走迷宫里面表现差别很大，BFS 可以保证找到最短路径，DFS 实现简单但是不一定是最短路线，A 星加入启发式估算，搜索效率最高，很多课程作业、单片机、Python、C 语言项目都是做老鼠走迷宫，同时还有实体版的智能小车模拟老鼠走迷宫，也就是硬件版迷宫寻路，和纯软件仿真版原理相通，都是基于网格地图判断上下左右四个方向能不能通行。

核心基础概念

老鼠走迷宫采用网格地图建模，迷宫由通道和墙体组成，每个格子是一个节点，老鼠只能在通道格子移动，不能穿过墙体，移动方向一般是上下左右四方向移动，部分拓展版本允许斜向八方向移动，起点标记为 S，终点标记为 E，墙体用 1 表示，通路用 0 表示。

老鼠走迷宫标准实现步骤

1. 定义二维数组作为迷宫地图，初始化起点坐标、终点坐标，标记墙体与可通行格子
2. 创建访问标记数组，记录老鼠已经走过的格子，防止重复走循环死路
3. 初始化搜索容器，BFS 使用队列，DFS 使用栈，A 星使用优先队列
4. 从起点开始，依次检测当前格子上下左右四个相邻格子，判断是否在地图边界内、不是墙体、没有访问过
5. 符合通行条件的相邻格子加入搜索容器，同时记录父节点信息，用来最后回溯还原完整路径
6. 循环执行搜索，当取出的节点等于终点，代表老鼠走迷宫寻路成功
7. 根据父节点反向回溯，从终点回推到起点，反转之后输出完整行走路径
8. 如果搜索容器全部清空依旧没有找到终点，判定迷宫不存在通路，老鼠无法到达出口

实体硬件版老鼠走迷宫要点

实体老鼠走迷宫一般是智能小车代替仿真老鼠，硬件由小车、红外传感器、单片机主控组成，红外传感器检测前方是否是墙壁，主控程序运行寻路算法，小车按照算法指令转向前进，硬件版本难点和软件仿真不一样，需要处理传感器误差、转向角度精度、电机打滑，很多硬件老鼠走迷宫还会增加记忆功能，第一次探索迷宫，第二次直接走已经记录好的最优路径。

路径回溯原理深度说明

老鼠走迷宫最容易出错的部分就是路径还原，单纯搜索只知道能不能到达终点，但是不会自动保存整条路线，所以每个节点都要保存上一步是从哪个格子过来的父坐标，找到终点之后，从终点沿着父坐标一路往回找，直到回到起点，这个就是回溯，很多初学者写老鼠走迷宫代码，搜索可以跑通，但是最后无法输出路径，就是没有保存父节点信息。

拓展进阶内容

老鼠走迷宫还可以做很多扩展改造，比如增加动态障碍，障碍物会随机变化，要求老鼠重新规划路线；增加多只老鼠并行寻路；增加惩罚机制，死路扣分，模拟强化学习版老鼠走迷宫，用奖励训练智能体自主学会找出口，这也是强化学习入门经典案例。

【相关 FAQ】

问题 1：老鼠走迷宫里面 BFS 为什么可以保证找到最短路径？

回答 1：老鼠走迷宫使用 BFS 广度优先搜索，是按距离起点层数逐层扩散，最先搜到终点的那条路线一定是步数最少，所以老鼠走迷宫的 BFS 算法可以保证得到最短路径。

问题 2：老鼠走迷宫 DFS 为什么经常不是最短路线？

回答 2：老鼠走迷宫的 DFS 是优先深入一条分支，遇到死路才回溯，它不会对比所有分支长度，优先找到通路就停止，所以老鼠走迷宫的 DFS 找到的路径不一定是最短路线。

问题 3：老鼠走迷宫 A 星算法相比 BFS 优势是什么？

回答 3：老鼠走迷宫 A 星算法加入启发距离估算，搜索的时候优先选择离终点更近的格子，相比 BFS 遍历更多节点，老鼠走迷宫 A 星搜索访问节点数量更少，大型迷宫寻路速度更快。

问题 4：实体小车版老鼠走迷宫和软件仿真老鼠走迷宫有什么区别？

回答 4：软件仿真老鼠走迷宫是纯代码运算，地图坐标是精确的，实体小车老鼠走迷宫依靠红外传感器识别墙体，存在传感器误差、电机转向偏差，硬件调试难度会更高。

【免责申明】

本文仅针对老鼠走迷宫算法原理、编程实验相关知识进行科普介绍，不提供侵权代码分发，相关算法属于公开通用计算机基础知识，请遵守相关法律法规。