1 引言

迷宫求解算法是计算科学中用于在结构化网格中寻找路径的经典方法。其应用横跨人工智能、游戏开发、机器人导航与电路设计等领域。这类算法的核心可追溯到图论中的路径搜索问题，而现代算法则融合了多种搜索策略，并常成为程序员展示创造力的舞台——比如在代码里让主角“永远撞南墙”也是一种浪漫。

1.1 迷宫的定义与数学建模

迷宫在计算机科学中被抽象为一个有限网格，每个单元格代表一个节点，单元格之间的邻接关系构成了图的边。

1.1.1 网格图的构建

将迷宫划分成规则的单元格，每个单元格与其上下左右（或包括对角线）的邻居相连，形成一个二维网格图。通常采用二维数组或矩阵来存储，每个元素对应一个单元格的状态。

1.1.2 可通行状态与障碍物

每个单元格被赋予一个二元状态：可通行（通常标记为0或空白）或障碍物（标记为1或墙壁）。起点与终点被指定为特殊单元格，而算法任务就是从起点出发，在可通行单元格中移动，最终抵达终点。

1.2 算法评估指标

评估一个迷宫求解算法的好坏，主要关注其运行效率与结果质量。

1.2.1 时间与空间复杂度

时间复杂度衡量算法运行所需的基本操作次数，通常用网格大小N（单元格总数）的函数表示。空间复杂度则衡量算法所需的内存，包括存储已访问节点、路径信息等。简而言之：先跑得快，再跑得好。

1.2.2 路径最优性保证

某些算法（如广度优先搜索、A*）保证找到最短路径；另一些（如深度优先搜索）只保证找到任意一条可行路径。按需选择，不要指望“乱走党”帮你省油钱。

2 盲目搜索算法

盲目搜索算法仅利用迷宫的结构信息，不依赖对目标位置的预估，按固定策略遍历节点。

2.1 深度优先搜索（DFS）

深度优先搜索沿着一条路径不断深入，直到撞墙或找到终点，再回溯探索其他分支。

2.1.1 递归回溯实现

递归实现是DFS最直观的形式：从当前节点出发，尝试所有方向，若邻居未访问则递归调用。代码简洁，但暗藏风险。

2.1.1.1 栈溢出的幽默后果

当迷宫足够大（如1000×1000且布局扭曲）时，递归深度可能超过系统栈限制，导致程序崩溃。这是程序员最初“我懂了”之后，直面“栈溢出”的经典瞬间——就像主角走到一半，突然被系统强制“退出游戏”。

2.1.2 非递归栈实现

使用显式栈（如C++的std::stack或Python的list）替代系统调用栈，可避免递归溢出的问题。算法逻辑不变，但程序员终于能安心睡个好觉——至少程序不会在半夜自己爆栈。

2.2 广度优先搜索（BFS）

广度优先搜索以起点为中心，逐层向外探索，如同水波扩散。

2.2.1 最短路径的保证

由于BFS按照距离起点的步数逐层推进，因此当它第一次到达终点时，所走路径就是最短路径。这是它的核心优势——特别适合“我要最短，绝不绕路”的强迫症患者。

2.2.2 队列与层序遍历

BFS使用队列存储待探索节点，每个节点在队首被处理，并将其邻居入队。通过追踪父节点指针，可以重构从起点到终点的路径。这使得BFS成为求最短路径的优选方案之一，尽管当迷宫巨大时，其内存消耗与网格大小成正比。

2.3 迭代加深搜索（IDS）

迭代加深搜索结合了DFS的空间效率与BFS的完备性。它反复执行带深度限制的DFS，并逐渐增加深度上限。

2.3.1 深度限制的调整

每次迭代的深度上限从1开始，每次增加1，直到找到目标或耗尽空间。尽管重复搜索看似浪费，但每次迭代的节点数呈指数增长，使得总体复杂度与BFS相当，且内存使用极小。这就像是“每次都多走一步的复读机”——最终总能把谜题破解。

3 启发式搜索算法

启发式搜索引入对目标位置的估计（称为启发函数），指导搜索向更有希望的方向前进。

3.1 A*算法

A*算法是启发式搜索的标杆，它结合了Dijkstra算法的路径代价计算与最佳优先搜索的贪心理念，通过评估函数f(n)=g(n)+h(n)选择节点。g(n)是从起点到n的真实代价，h(n)是从n到终点的估计代价。

3.1.1 启发函数的设计（曼哈顿距离、欧几里得距离）

启发函数是A*的灵魂。常用的启发函数包括：

  • 曼哈顿距离：适用于只能上下左右移动的网格，计算横向与纵向的绝对值之和。
  • 欧几里得距离：适用于允许对角线移动的网格，计算直线距离。
3.1.1.1 用“直线飞过去”的骗术

如果h(n)过高估计了实际距离（比如在只能走“十”字路的迷宫里用欧几里得距离），A*可能无法找到最短路径，但能更快地收敛。这是算法界的“智商税”——与“跨越一堵墙，直线飞过去”的幻想类似，虽然有时能歪打正着，但结果可能并不完美。

3.2 Dijkstra算法

Dijkstra算法可以看作A*的“古董版”，其中h(n)恒为0，即仅根据已走代价选择节点。它保证找到最短路径，但探索范围比A*大得多。

3.2.1 权重统一时的退化

当网格中所有边的权重等于1时，Dijkstra算法退化为广度优先搜索。这如同让一辆涡轮增压跑车在限速30的小巷里爬行——效率感人但毫无必要。

最佳优先搜索只依赖启发函数h(n)，不考虑已走代价，每次都选择看起来离终点最近的节点进行扩展。

3.3.1 贪心陷阱：被墙角骗的机器人

由于完全忽略走过的路，最佳优先搜索可能被局部最优解吸引，比如被一面“看起来很接近”的墙反复欺骗，最终在死胡同里打转。这就像一台导航仪告诉你“前方直行100米到达”，结果你撞上了一堵墙。

4 经典生物学启发算法

从动物行为和数学实验中汲取灵感的算法，往往简单而有趣。

4.1 右手定则与墙随法

右手定则又称“墙随法”：始终保持右手或左手贴着墙壁行走，若遇到岔路，优先选择能让手附着在新墙壁上的方向。

4.1.1 单连通迷宫的万能钥匙

对于单连通迷宫（所有墙壁连为一体且无环路），右手定则保证能从任何起点走到任何出口。这是迷宫学校的“毕业证书”——简单易懂，绝对可靠，除非迷宫本身搞鬼。

4.1.2 死胡同的循环悖论

当迷宫存在环状结构（有环路）时，右手定则可能让行者在环中无限循环。这如同绕圈圈的仓鼠——快乐而徒劳，最终需要人为干预或更智能的策略来打破僵局。

4.2 Tremaux算法（标记法）

19世纪法国数学家Tremaux提出了一种使用标记来避免重复路径的算法。

4.2.1 粉笔标记的数学原理

该算法模拟在迷宫中用粉笔做标记：每经过一条通道，在入口和出口各画一条线。决策规则简单：优先选择未标记的通道；若通道标记数量已为2，则不得再走；若陷入无路可走，则退回并重新标记。通过这种“一画一擦”的方式，最终能找到出口。

4.2.2 在迷宫竞赛中的应用

Tremaux算法是许多迷宫竞赛（如国际迷宫挑战赛）的标准策略。参赛者只需一支粉笔和一条纪律，即可在复杂迷宫中立于不败之地。它也被用于早期的扫地机器人路径规划——毕竟，擦地时也要用“粉笔”留下痕迹。

4.3 随机游走策略

随机游走：在岔路口随机选择方向，完全放弃任何记忆和策略。

4.3.1 最终一定会走到终点的数学证明（但可能需时∞）

数学上，对于有限、连通的迷宫，随机游走在无限时间内到达任意节点的概率为1。这意味着“瞎猫撞上死耗子”是必然事件——但有可能等你撞到出口时，人类已经进化出了飞天遁地的能力。生活中请勿模仿，除非你只想证明算法在统计意义上的可靠性。

5 算法变种与优化

针对特定场景的改进方案，提升了基础算法的效率与实用性。

5.1 双向搜索

双向搜索分别从起点和终点同时进行搜索，当双方的交集出现时，路径即构建完成。

5.1.1 从起点和终点同时挖洞

想象两支工程队从隧道两端同时开挖，相遇时便打通了通道。双向BFS可以将搜索范围缩减为单向BFS的一半（严格来说约相当于开根号），在巨大迷宫中优势明显。这是“双向奔赴”的算法版，快推快出。

5.2 分层与缩略图（Hierarchical Pathfinding）

先构建迷宫的缩略视图（粗粒度图），再在缩略图上找到高层路径，最后在细粒度图中进行局部搜索。

5.2.1 先看地图再走路

好比出门旅游时先看城市交通地图，再规划街道级别的路线。分层方法显著减少了搜索节点数，适合动态迷宫（如游戏中怪物巡逻）与超大场景。毕竟，没人会在纽约市里用DFS方式每个街区逐个探索——连GPS都知道开高速要比走巷子快。

5.3 跳点搜索（JPS）

跳点搜索是A*在网格图上的优化变种，通过跳过对称的、无信息量的节点来加速搜索。

5.3.1 省去冗余邻居的暴力美学

JPS假设网格中只有两种节点：可通行与障碍。它预先检测当前方向上的“跳点”（强制邻居出现的位置），并在到达跳点前一次性跳过中间大量无差异的格子。这堪称算法界的“快进键”——跳过无聊的直线段，直达关键位置。需要暴力，但很优雅。

6 性能对比与选型指南

根据实际需求选择合适算法，往往比强行使用理论最优算法更明智。

6.1 时间复杂度实验数据

在典型测试中，对于100×100的迷宫：

  • DFS平均耗时0.1ms（但可能绕远路）
  • BFS耗时0.5ms（保证最短）
  • A*耗时0.3ms（综合最优）
  • 随机游走——可能耗时等价于“看完三遍《指环王》”

6.1.1 小迷宫选DFS，大迷宫选A*

小迷宫（如1000节点以下）中，DFS凭借极低的实现成本和超快速度胜出；大型迷宫（百万级节点）中，A*的引导机制显著减少无效搜索。一句话：迷宫小到可以随便玩，就用DFS；大到需要地图，就上A*。

6.2 空间消耗的取舍

DFS仅需栈空间（O(N)最坏情况），BFS需要队列存储当前层节点（O(N)），A*需要优先队列与父节点映射（O(N)）。

6.2.1 内存不足时的玄学调参

当内存吃紧时，可尝试迭代加深搜索（有限内存）或随机游走（无内存），但后者极可能让你“生死有命，富贵在天”。如果条件允许，改用双向搜索或分层方法也能缓解内存压力。记住：没有万能的银弹，只有灵活的调参玄学。

7 应用场景

算法从纸面走向现实，解决实际问题。

7.1 游戏AI中的寻路（《吃豆人》如何不撞墙）

经典游戏《吃豆人》中的鬼怪AI使用BFS或A*追踪玩家，而玩家则依靠模式化的移动规则来逃避追捕。现代游戏（如《文明》系列）则使用分层A*处理成千上万个单位的寻路请求。

7.2 机器人吸尘器的路线规划

家用扫地机器人通常组合右手定则（清理边界）与随机游走（覆盖开放区域），以避免重复清扫。高端机型则使用SLAM技术结合A*，让机器人既不撞墙也不漏扫。

7.3 芯片布线与电路板设计

在VLSI（超大规模集成电路）设计中，布线算法使用改进的A*搜索在多层网格中找到最短且无冲突的金属连线，这是迷宫求解的工业级应用——一旦走错，千万晶体管买单。

7.4 都市传说：用迷宫算法找停车位

坊间流传有人用迷宫求解算法编写程序，在大型购物中心停车场寻找空位。显然，该算法大多会输出“方案已找到，但停车场入口已关闭”的提示——因为现实中的迷宫远比代码复杂。

8 彩蛋与幽默

8.1 如果让一只猫代替算法

让猫代替算法执行迷宫求解：猫可能在岔路口的纸箱里睡着，或者莫名其妙地绕回起点。最终，算法收敛于“猫醒了，随缘前进”。结论：猫是实现“零收敛时间”的算法，但结果总是“喵”。

8.1.1 猫可能会睡着在死胡同

如果猫咪进入死胡同，它极可能就地躺下，睡个午觉。这时，算法陷入了“无限阻塞”状态，直到你按F5（重启）或拎起猫脖子移动。因此，任何生产环境都严禁使用猫算法。

8.2 程序员用递归解迷宫时的心路历程

第一阶段：“递归如此优雅，我一定是最聪明的程序员！” 第二阶段：“为什么这个迷宫让程序卡了30秒？” 第三阶段：“Stack overflow! 我怎么又忘了把递归深度写进需求里？”

8.2.1 从“我懂了”到“栈溢出”

这是每个程序员在捣鼓迷宫时的必经之路。当你满怀信心地提交代码，看到终端输出“Segmentation fault”时，你终于悟到：迷宫真正的解，其实是手动增大栈空间——或者更优雅地，改用迭代。