Python基于DFS算法实现迷宫全量可行解检索的问题咨询
迷宫全量可行解的DFS改造指南
原单路径脚本的核心局限
原脚本的设计逻辑天然只支持返回第一条找到的路径,根源有三点:
- 遍历四个邻接方向时,只要某一分支返回了非空的路径结果,就立刻拼接当前节点并直接返回,完全不会继续遍历剩余方向的其他分支
- 进入节点后直接将其标记为
explored,没有后续的状态回溯机制,节点一旦被标记就会永久排除在后续遍历范围外 - 递归函数的返回值为单条路径/空列表,没有可以承载多结果的收集容器
改造核心逻辑
要实现全量路径检索,不需要改变DFS的核心搜索框架,只需要调整三个递归环节的运行规则:
- 移除提前返回的逻辑:不再在拿到第一个有效路径时直接终止递归,而是收集所有邻接方向返回的有效路径
- 增加路径与访问状态的回溯机制:在当前节点的所有邻接分支遍历完成后,将当前节点从当前遍历路径中移除,同时将其
explored状态恢复为可通行,保证其他分支可以正常经过该节点 - 调整递归返回值结构:DFS函数不再返回单条路径,而是返回从当前节点出发能够到达出口的所有路径组成的列表,每个节点拿到子分支的路径列表后,拼接自身位置即可形成完整路径
改造后可运行代码
注:代码中
lett单元格直接按可通行path处理,无需特殊判断
def DFS_all(x, y, Map, current_path=None): all_paths = [] # 首次调用时初始化当前遍历路径 if current_path is None: current_path = [] # 碰到出口:将当前完整路径存入结果集 if Map[x][y] == "exit": all_paths.append(current_path + [(x, y)]) return all_paths # 碰到不可通行的墙直接终止该分支 if Map[x][y] not in ("path", "lett"): return all_paths # 标记当前节点为已探索,同时加入当前遍历路径 current_path.append((x, y)) Map[x][y] = "explored" # 遍历四个邻接方向 for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]: next_x, next_y = x + dx, y + dy # 递归获取邻接节点出发的所有有效路径 sub_paths = DFS_all(next_x, next_y, Map, current_path) all_paths.extend(sub_paths) # 回溯操作:移除当前节点的探索标记,从当前路径中移除当前节点 current_path.pop() if Map[x][y] == "explored": Map[x][y] = "path" return all_paths def GetMap(): return [ ["wall","wall","wall","wall","wall","wall","wall","wall"], ["wall","path","path","path","path","path","path","wall"], ["wall","wall","wall","path","wall","lett","path","wall"], ["wall","path","path","path","wall","wall","path","wall"], ["wall","path","wall","lett","path","path","path","wall"], ["wall","path","wall","wall","wall","wall","path","wall"], ["wall","path","lett","path","path","path","exit","wall"], ["wall","wall","wall","wall","wall","wall","wall","wall"] ] def DrawMap(Map,path): for x in range(0,len(Map)): for y in range(0,len(Map[x])): if ((x,y) in path): assert Map[x][y] in ("path","lett","exit") print("-",end="") elif (Map[x][y]=="wall"): print("#",end="") elif (Map[x][y]=="exit"): print("e",end="") elif (Map[x][y]=="lett"): print("L",end="") else: print(' ',end="") print() # 全路径检索测试 if __name__ == "__main__": print("Unsolved:\n") DrawMap(GetMap(), []) print("\n") maze_map = GetMap() all_found_paths = DFS_all(1, 1, maze_map) print(f"共检索到{len(all_found_paths)}条可行解\n") for path_idx, single_path in enumerate(all_found_paths): print(f"第{path_idx+1}条路径,总长度{len(single_path)}:") DrawMap(GetMap(), single_path) print()
运行注意事项
- 递归过程中的状态回溯是必须环节,缺少回溯会导致其他分支经过已探索节点时被误判为阻挡,最终漏算合法路径
- 每次绘制路径时需要重新调用
GetMap()生成新的迷宫实例,因为递归过程中会修改原迷宫的单元格状态,复用原迷宫对象会导致绘制异常
内容的提问来源于stack exchange,提问作者Deryckere Frederico
相关产品推荐
相关产品推荐

