Python实战案例：递归实现迷宫寻路
文章目录
一、案例背景
在学习了递归的基本概念后，我们现在要通过一个经典的迷宫问题来加深对递归的理解。
本文将展示一个迷宫自动寻路案例，通过实际代码演示递归在路径搜索中的应用。
案例描述
假设我们有一个5×5的迷宫：
1代表墙壁（不可通过）0代表通路（可以通过）- 入口在(0,2), 即
maze[0][2] - 出口在(4,3), 即
maze[4][3]
迷宫地图如下：
maze = [
[1, 1, 0, 1, 1], # 第0行
[1, 0, 0, 0, 1], # 第1行
[1, 0, 1, 1, 1], # 第2行
[1, 0, 0, 0, 1], # 第3行
[1, 1, 1, 0, 1] # 第4行
]
我们需要运用我们所学习的递归的相关知识，求解出这个迷宫的有效通路
二、 递归求解思路
2.1 基本框架
当我们通过递归函数find_path()对该迷宫求解时，需要实现以下逻辑：
- 基线条件：如果当前位置是出口，返回路径坐标列表
- 边界检查：确保坐标在迷宫范围内
- 碰撞检测：检查当前位置是否可通行
- 标记路径：将当前位置标记为已访问
- 递归探索：尝试四个方向（下、右、上、左）探索
- 回溯处理：如果四个方向都走不通，标记为死路，返回上一节点，继续探索
2.2 代码实现
def find_path(start_a, start_b, end_a, end_b, path=None):
"""
递归搜索迷宫路径的核心函数
参数说明：
start_a, start_b: 起点的行、列索引(例如入口是0,2)
end_a, end_b: 终点的行、列索引(例如出口是4,3)
path: 当前路径记录（保存经过的坐标点）
返回值：
成功时返回路径坐标列表, 失败返回None
"""
# 首次调用时检查进出口坐标合法性并初始化路径列表
if path is None:
# 检查入口坐标合法性
if not (0 <= start_a < len(maze) and 0 <= start_b < len(maze[0])):
print(f"入口坐标({start_a},{start_b})超出迷宫范围")
return None
# 检查出口坐标合法性
if not (0 <= end_a < len(maze) and 0 <= end_b < len(maze[0])):
print(f"出口坐标({end_a},{end_b})超出迷宫范围")
return None
# 检查入口和出口是否可通行
if maze[start_a][start_b] != 0:
print(f"入口({start_a},{start_b})不可通行")
return None
elif maze[end_a][end_b] != 0:
print(f"出口({end_a},{end_b})不可通行")
return None
path = []
# 递归出口：到达终点
if start_a == end_a and start_b == end_b:
print("★ 找到出口 ★ ")
final_path = path + [(end_a, end_b)] # 将出口坐标加入路径
print("完整路径:", final_path)
return final_path
# 边界检查：确保当前位置在迷宫范围内
if not (0 <= start_a < len(maze) and 0 <= start_b < len(maze[0])):
print(f"错误: 位置({start_a},{start_b})超出迷宫范围")
return None
# 检查当前位置是否可通行
if maze[start_a][start_b] != 0:
print("遭遇碰撞，重新规划路线".center(30, "="))
return None
# 标记当前路径点（防止重复经过）
maze[start_a][start_b] = 2 # 2表示已走过的路径
current_path = path + [(start_a, start_b)] # 将当前位置加入路径
print(f"标记路径点: ({start_a},{start_b})")
print("当前路径进展:", current_path)
# 定义方向字典(键:值=方向:坐标偏移量)
directions = {
"下": (1, 0), # 向下
"右": (0, 1), # 向右
"上": (-1, 0), # 向上
"左": (0, -1), # 向左
}
# 递归遍历四个方向
for k, v in directions.items():
da, db = v # 解包字典的值(坐标偏移量)
next_a, next_b = start_a + da, start_b + db # 计算下一个位置的坐标
# 打印提示信息
print(f"尝试向{k}移动至 → 新位置({next_a},{next_b})")
# 递归调用：尝试向该方向移动
result = find_path(next_a, next_b, end_a, end_b, current_path)
# 如果递归返回有效路径，直接传递结果到上层
if result:
return result
# 程序执行到这里.证明四个方向遍历结束
# 但是所有方向都走不通：坐标点标记为死路
maze[start_a][start_b] = 3 # 3表示死胡同
print(f"标记死路点: ({start_a},{start_b})")
return None
# 定义迷宫数据
maze = [
[1, 1, 0, 1, 1], # 第0行
[1, 0, 0, 0, 1], # 第1行
[1, 0, 1, 1, 1], # 第2行
[1, 0, 0, 0, 1], # 第3行
[1, 1, 1, 0, 1] # 第4行
]
# 调用函数开始迷宫寻路
print("===== 迷宫求解开始 =====")
final_path = find_path(
start_a=0, start_b=2, # 入口坐标
end_a=4, end_b=3 # 出口坐标
)
# 输出最终结果
if not final_path:
print("未找到可行路径")
else:
print("\n最终路径坐标序列：")
for step, (row, col) in enumerate(final_path):
print(f"第{step + 1}步 → 行：{row}, 列：{col}")
三、执行过程分析
让我们跟踪程序的执行流程：
- 从入口(0,2)开始
- 标记(0,2)为已访问
- 尝试向下移动至(1,2)
- 标记(1,2)为已访问
- 尝试向下移动至(2,2) → 遇到墙壁
- 尝试向右移动至(1,3)
- 标记(1,3)为已访问
- 尝试向下移动至(2,3) → 遇到墙壁
- …
- 最终找到路径：
(0,2)→(1,2)→(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(4,3) - 打印分步结果：
最终路径坐标序列： 第1步 → 行：0, 列：2 第2步 → 行：1, 列：2 第3步 → 行：1, 列：1 第4步 → 行：2, 列：1 第5步 → 行：3, 列：1 第6步 → 行：3, 列：2 第7步 → 行：3, 列：3 第8步 → 行：4, 列：3
四、关键点解析
4.1 递归终止条件
当函数到达出口坐标(4,3)时，递归终止。这是递归的基线条件。
4.2 路径标记与回溯
我们使用三个值来表示迷宫状态：
0：未访问的通路
2：已访问的有效路径
3：死路
这种标记方式使得程序能够：
1. 避免重复访问
2. 在回溯时识别无效路径
4.3 方向探索顺序
我们按照"下、右、上、左"的顺序尝试移动。
这个顺序决定了算法的搜索策略为深度优先搜索（DFS），
特点是优先向一个方向探索到底，直到无法继续才回溯(即不撞南墙,不回头)。
注意：
不同的方向顺序会影响找到的路径(可根据进出口位置调整)，但不影响最终结果的正确性。
若迷宫存在多条路径，DFS 找到的可能不是最短路径。
代码验证:
五、案例缺陷
- 由于探索方向的在函数内固定，如果迷宫存在多条通路,我们最终得出的结果，可能不是最优路径(如上图)
- 由于Python中递归深度的限制，此方式并不适合过于复杂的迷宫
- 灵活性缺乏，此案例过度依赖用户输入进出口位置坐标，如果输入有误，会得到错误路径
- 效率相对较低，程序可能朝着一个方向探索多次，结果是一条死路
六、案例总结
通过这个迷宫求解实例，我们看到了递归在解决实际问题时的强大能力。关键点在于：
- 明确定义递归终止条件
- 正确处理回溯
- 合理标记访问状态
递归虽然强大，但由于Python中递归其自身的限制，此案例仅用于演示递归的用法。
在实际应用中，对于大型复杂迷宫，我们可能需要考虑使用其他算法(广度优先搜索（BFS）、A * 算法)。