Python求解迷宫的三种算法：递归、回溯与队列详解
本文深入解析Python中求解迷宫问题的三种核心算法：递归、回溯与队列。通过二维列表构建迷宫模型，详细阐述递归的深度探索机制、基于栈的回溯策略以及基于队列的广度优先搜索。文章提供完整代码逻辑与可视化示例，帮助开发者理解不同算法在路径查找中的优劣与适用场景。
前言
针对迷宫问题，即在给定入口与出口坐标的前提下寻找连通路径，本文重点探讨三种经典的求解策略：递归法、回溯法以及队列法。
在深入算法细节前，需先建立迷宫的数据模型。通常采用二维列表（List嵌套List）来存储迷宫结构。在数据表示上，数值1代表障碍物或不可通行区域，0代表可通行区域，而数值2则用于标记已访问过的路径节点，以避免重复遍历。
递归求解
递归求解的核心逻辑基于深度优先搜索思想，具体步骤如下：
- 系统维护一个当前坐标指针，初始状态指向迷宫入口。
- 若当前坐标与出口坐标重合，则判定路径查找成功。
- 若当前坐标四周均无可行路径，则判定当前分支探查失败，需执行回退操作，即返回至上一级节点。
- 选取当前节点的一个可行相邻节点，递归执行上述探查逻辑。若从该相邻节点能成功抵达出口，则当前节点至出口的路径即告成立。
算法启动时，将迷宫入口坐标作为初始检查点，整体执行流程如下：
- 对当前节点进行标记（通常标记为2），表示已访问。
- 判断当前节点是否为出口，若是则直接返回成功状态。
- 依次检查当前节点上下左右四个相邻节点，递归调用自身以判断其是否可达出口。
- 若四个方向的递归探查均返回失败，则向上传递失败信号。
dirs=[(0,1),(1,0),(0,-1),(-1,0)] #当前位置四个方向的偏移量
path=[] #存找到的路径
def mark(maze,pos): #给迷宫maze的位置pos标"2"表示“倒过了”
maze[pos[0]][pos[1]]=2
def passable(maze,pos): #检查迷宫maze的位置pos是否可通行
return maze[pos[0]][pos[1]]==0
def find_path(maze,pos,end):
mark(maze,pos)
if pos==end:
print(pos,end=" ") #已到达出口，输出这个位置。成功结束
path.append(pos)
return True
for i in range(4): #否则按四个方向顺序检查
nextp=pos[0]+dirs[i][0],pos[1]+dirs[i][1]
#考虑下一个可能方向
if passable(maze,nextp): #不可行的相邻位置不管
if find_path(maze,nextp,end):#如果从nextp可达出口，输出这个位置，成功结束
print(pos,end=" ")
path.append(pos)
return True
return False
def see_path(maze,path): #使寻找到的路径可视化
for i,p in enumerate(path):
if i==0:
maze[p[0]][p[1]] ="E"
elif i==len(path)-1:
maze[p[0]][p[1]]="S"
else:
maze[p[0]][p[1]] =3
print("\n")
for r in maze:
for c in r:
if c==3:
print('\033[0;31m'+"*"+" "+'\033[0m',end="")
elif c=="S" or c=="E":
print('\033[0;34m'+c+" " + '\033[0m', end="")
elif c==2:
print('\033[0;32m'+"#"+" "+'\033[0m',end="")
elif c==1:
print('\033[0;;40m'+" "*2+'\033[0m',end="")
else:
print(" "*2,end="")
print()
if __name__ == '__main__':
maze=[[1,1,1,1,1,1,1,1,1,1,1,1,1,1],\
[1,0,0,0,1,1,0,0,0,1,0,0,0,1],\
[1,0,1,0,0,0,0,1,0,1,0,1,0,1],\
[1,0,1,0,1,1,1,1,0,1,0,1,0,1],\
[1,0,1,0,0,0,0,0,0,1,1,1,0,1],\
[1,0,1,1,1,1,1,1,1,1,0,0,0,1],\
[1,0,1,0,0,0,0,0,0,0,0,1,0,1],\
[1,0,0,0,1,1,1,0,1,0,1,1,0,1],\
[1,0,1,0,1,0,1,0,1,0,1,0,0,1],\
[1,0,1,0,1,0,1,0,1,1,1,1,0,1],\
[1,0,1,0,0,0,1,0,0,1,0,0,0,1],\
[1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
start=(1,1)
end=(10,12)
find_path(maze,start,end)
see_path(maze,path)代码中提供的see_path函数可用于在控制台直观展示查找到的路径，运行输出示例如下：
其中，S标识入口位置，E标识出口位置，*符号代表最终确定的有效路径，#符号代表算法探索过程中经过但非最终路径的节点。
回溯求解
回溯法主要利用栈（Stack）数据结构来存储待探索的节点。利用栈“后进先出”的特性，当某条分支探索失败时，程序自动回退至栈顶最近保存的可探索节点。这本质上是一种深度优先搜索（DFS）的实现方式。
def maze_solver(maze,start,end):
if start==end:
print(start)
return
st=SStack()
mark(maze,start)
st.push((start,0)) #入口和方向0的序对入栈
while not st.is_empty(): #走不通时回退
pos,nxt=st.pop() #取栈顶及其检查方向
for i in range(nxt,4): #依次检查未检查方向，算出下一位置
nextp = pos[0] + dirs[i][0], pos[1] + dirs[i][1]
if nextp==end:
print_path(end,pos,st) #到达出口，打印位置
return
if passable(maze,nextp): #遇到未探索的新位置
st.push((pos,i+1)) #原位置和下一方向入栈
mark(maze,nextp)
st.push((nextp,0)) #新位置入栈
break #退出内层循环，下次迭代将以新栈顶作为当前位置继续
print("找不到路径")队列求解
队列法利用队列（Queue）数据结构存储待探索节点。借助队列“先进先出”的特性，算法在每个分支层级上同步扩展搜索范围，直至发现出口。这属于广度优先搜索（BFS）的典型应用。
def maze_solver_queue(maze,start,end):
path.append(start)
if start==end:
print("找到路径")
return
qu=SQueue()
mark(maze,start)
qu.enqueue(start) #start位置入队
while not qu.is_empty(): #还有候选位置
pos=qu.dequeue() #取出下一位置
for i in range(4): #检查每个方向
nextp = pos[0] + dirs[i][0], pos[1] + dirs[i][1]
if passable(maze,nextp): #找到新的探索方向
if nextp==end: #是出口，成功
print("找到路径")
path.append(end)
return
mark(maze,nextp)
qu.enqueue(nextp) #新位置入队
path.append(nextp)
print("未找到路径")需要注意的是，队列法直接运行仅能判定路径是否存在，无法直接输出具体路径序列。若需获取具体路径，需额外引入链表等存储结构来记录节点间的父子关系。
总结
本文介绍了利用Python解决迷宫问题的三种主要实现方式。更多Python算法相关内容，建议参考本站过往文章或持续关注后续更新，感谢支持。
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
