You need to enable JavaScript to run this app. Python基于DFS算法实现迷宫全量可行解检索的问题咨询
优惠活动
大模型
产品
解决方案
定价
更多

Python基于DFS算法实现迷宫全量可行解检索的问题咨询

迷宫全量可行解的DFS改造指南

原单路径脚本的核心局限

原脚本的设计逻辑天然只支持返回第一条找到的路径,根源有三点:

  • 遍历四个邻接方向时,只要某一分支返回了非空的路径结果,就立刻拼接当前节点并直接返回,完全不会继续遍历剩余方向的其他分支
  • 进入节点后直接将其标记为explored,没有后续的状态回溯机制,节点一旦被标记就会永久排除在后续遍历范围外
  • 递归函数的返回值为单条路径/空列表,没有可以承载多结果的收集容器

改造核心逻辑

要实现全量路径检索,不需要改变DFS的核心搜索框架,只需要调整三个递归环节的运行规则:

  1. 移除提前返回的逻辑:不再在拿到第一个有效路径时直接终止递归,而是收集所有邻接方向返回的有效路径
  2. 增加路径与访问状态的回溯机制:在当前节点的所有邻接分支遍历完成后,将当前节点从当前遍历路径中移除,同时将其explored状态恢复为可通行,保证其他分支可以正常经过该节点
  3. 调整递归返回值结构: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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.11 03:45:10