如何让回溯技术高效求解大型迷宫？

嘿，我完全懂你这种坚持用回溯法的执念——虽然知道BFS这类算法找最短路径更高效，但就是想把回溯的路子走通对吧？针对你说的15x15迷宫就卡住的问题，其实核心是回溯的暴力搜索在大迷宫里分支太多，得给它加几个“刹车”和“导航”，分享几个亲测有效的优化点：

• 提前用已知最短路径剪枝：
  你要找的是最短路径，那只要我们先找到一个可行解，记录它的长度，之后所有递归分支里，只要当前路径的长度已经超过这个已知最短长度，直接终止这条分支的搜索——反正再往下走也不可能得到更短的路径了。甚至可以一开始先估算一个最大可能的最短路径长度（比如15x15的迷宫，最短路径最多是15+15-2=28步，去掉障碍的影响可以设个30左右的初始值），超过这个值就停，找到第一个解后再把这个值更新成实际最短长度，后面的分支就会被大量剪掉。

• 给8个方向排优先级：
  别乱序尝试8个方向，优先往靠近终点的方向走。比如终点在右下角，那先试右下、右、下这几个方向，再试其他方向。这样能更快找到一个较优的短路径，然后用这个路径长度去剪其他分支，大大减少无效搜索的次数。毕竟回溯最怕在远离终点的分支里瞎逛半天。

• 标记当前路径的已访问格子（记得回溯时撤销）：
  很多人容易忽略这一点：在递归进入某个格子时，把它标记为“已在当前路径中”（比如临时设为2），回溯离开时再改回原来的0。这样能避免在同一条搜索分支里绕圈（比如走A→B→A这种死循环），直接砍掉大量重复的无效递归。注意别把这个标记永久化，否则会错过其他分支里可能的更短路径。

• 递归前先做“预检查”：
  不要一上来就递归，先判断当前格子：是不是越界了？是不是障碍（1）？是不是已经在当前路径里了？只要有一个不符合，直接返回，不用进入递归函数。把这些判断放在递归入口前，能减少很多不必要的函数调用开销。

• 避免重复计算相同状态：
  可以用一个二维数组记录每个格子的最短到达步数，如果当前走到这个格子的步数已经比之前记录的步数多，直接放弃这条分支。比如之前已经用3步走到了格子(x,y)，现在又用5步走到这里，那后面再怎么走也不可能比之前的路径短，直接终止就行。

最后提醒一下，回溯法本身的时间复杂度还是比较高的，15x15已经是个不小的规模，但加了这些优化后，应该能顺利跑起来。

内容来源于stack exchange