老鼠走迷宫与回溯 · Learning Notes

老鼠走迷宫是在网格上寻找从入口到出口的路径。回溯法沿一条路走到底，遇到死路就退回上一个分叉，换方向再试。本页说明迷宫的表示、四个方向的搜索顺序、访问标记和失败标记，并给出完整实现。回溯的逐层调用与返回依赖递归；若要找最短路径或比较不同路径的代价，应改用广度优先搜索或最短路径算法，而不只是找一条可行路径。

定义

回溯法按顺序尝试候选解：选择一个候选后递归进入下一层；若沿这个选择无法到达目标，就放弃它，回到上一层尝试下一个候选。与单纯递归枚举的区别是失败后要处理这个候选留下的状态——恢复原状，或标记为已确认不可行，让其他分支能在正确的局面上继续。

用二维列表m表示迷宫，每个格子取以下值之一：

0：可以走的格子；
1：墙；
2：当前路径上的格子，进入时标记；
3：已经确认从这里走不到出口的格子，回溯时标记。

入口是 (sta1, sta2)，出口是 (fsh1, fsh2)。每一步只能走上、下、左、右四个相邻格子，不能斜走。

性质

搜索步骤

标记当前格子

进入 (i, j) 后先令m[i][j] = 2，表示这个格子已经访问，防止搜索绕回自己。
检查是否到达出口

若 (i, j) 就是出口，令全局标志success = 1，随后逐层返回。
按固定顺序尝试四个方向

依次检查上、下、左、右。若相邻格子为0且尚未找到出口，就递归进入该格子。
失败则标记并返回

四个方向都没有找到出口时，把m[i][j] 改为3，表示从这里出发走不通，再返回上一层。

标记的作用

2和3都让格子不再以0的身份被再次进入，但含义不同：

2是当前搜索路径的一部分。搜索还在进行时，它阻止回到路径上的格子，避免在环里无限递归。
3是已经验证过的死路。从别的方向到达同一个格子，结果仍然是走不通，所以可以直接跳过。

找到一条路径就停止

success是全局标志。一旦某次递归到达出口，其余方向不再尝试，所有调用依次返回。这样得到的是一条可行路径，不保证最短。若要找最短路径，应使用按层扩展的广度优先搜索；若要枚举所有路径，失败后必须把格子恢复为0，而不是标成3。

边界与代价

代码依赖迷宫最外圈全是1：向上、向左越界时，Python的负索引取到的是另一侧的墙；向下越界不会发生，因为最底行是墙，搜索不会进入；这个迷宫的最右列除出口外都是墙，而到达出口后success已经置1，后续方向检查被短路。

每个格子最多被访问一次，时间复杂度为 $O(rc)$ （ $r$ 行、 $c$ 列）；递归深度最多等于路径长度，最坏情况下为 $O(rc)$ ，大迷宫可能超过Python的默认递归深度。

例子

完整实现：找到一条通路

1
m = [
2
    [1, 1, 1, 0, 1, 1, 1, 1, 1, 1],
3
    [1, 0, 0, 0, 0, 0, 0, 0, 1, 1],
4
    [1, 0, 1, 1, 1, 1, 1, 0, 0, 1],
5
    [1, 0, 1, 0, 0, 0, 0, 1, 0, 1],
6
    [1, 0, 1, 0, 1, 1, 0, 0, 0, 1],
7
    [1, 0, 0, 1, 1, 0, 1, 0, 1, 1],
8
    [1, 1, 1, 1, 0, 0, 0, 0, 1, 1],
9
    [1, 0, 0, 0, 0, 1, 1, 1, 0, 0],
10
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
11
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
12
]
13

14
sta1 = 0
15
sta2 = 3
16
fsh1 = 7
17
fsh2 = 9
18
success = 0
19

20

21
def LabyrinthRat():
22
    print("显示迷宫：")
23
    for i in range(len(m)):
24
        print(m[i])
25
    print("入口：m[%d][%d]：出口：m[%d][%d]" % (sta1, sta2, fsh1, fsh2))
26
    if (visit(sta1, sta2)) == 0:
27
        print("没有找到出口")
28
    else:
29
        print("显示路径：")
30
        for i in range(10):
31
            print(m[i])
32

33

34
def visit(i, j):
35
    m[i][j] = 2
36
    global success
37
    if (i == fsh1) and (j == fsh2):
38
        success = 1
39
    if (success != 1) and (m[i - 1][j] == 0):
40
        visit(i - 1, j)
41
    if (success != 1) and (m[i + 1][j] == 0):
42
        visit(i + 1, j)
43
    if (success != 1) and (m[i][j - 1] == 0):
44
        visit(i, j - 1)
45
    if (success != 1) and (m[i][j + 1] == 0):
46
        visit(i, j + 1)
47
    if success != 1:
48
        m[i][j] = 3
49
    return success
50

51

52
if __name__ == "__main__":
53
    LabyrinthRat()

程序结束后，m中值为2的格子连成从入口到出口的路径，值为3的格子是搜索过程中试过但走不通的分支。对这个迷宫，路径从 (0,3) 进入，先向下再向右，绕过若干死路后到达 (7,9)。

LabyrinthRat输出路径时的range(10) 与迷宫行数绑定；换一份尺寸不同的迷宫，这个数字要一起改。

交互探索

逐步查看搜索如何进入相邻格子、在死路回退，并保留访问标记。

走到死路后，搜索怎样回退？

逐步观察深度优先搜索在迷宫中的访问和回溯。