Python寻路算法优化求助：迷宫最少遇怪安全路径求解

问题背景 #

给定n×n迷宫，其中：

• . 代表地板格
• # 代表墙壁格
• @ 代表怪物格

玩家从左上角起点出发，仅能向右或向下移动，目标是到达右下角终点，需找到遇怪数量最少的安全路径。现有回溯算法在处理20×20这类大尺寸迷宫时，运行速度骤降，需要优化方案。

原算法代码：

def count(r):
    n = len(r)
    visited = [[False for j in range(n)] for i in range(n)]
    paths = []
 
    def pathfind(i, j, path, monster_count):
        if i == n - 1 and j == n - 1:
            paths.append((path, monster_count))
            return
        
        visited[i][j] = True
 
        if i + 1 < n and not visited[i + 1][j] and r[i + 1][j] != '#':
            if r[i + 1][j] == '@':
                pathfind(i + 1, j, path + [(i + 1, j)], monster_count + 1)
 
            else:
                pathfind(i + 1, j, path + [(i + 1, j)], monster_count)
 
        if j + 1 < n and not visited[i][j + 1] and r[i][j + 1] != '#':
            if r[i][j + 1] == '@':
                pathfind(i, j + 1, path + [(i, j + 1)], monster_count + 1)
 
            else:
                pathfind(i, j + 1, path + [(i, j + 1)], monster_count)
 
        visited[i][j] = False
 
    if r[0][0] == '@':
        pathfind(0, 0, [(0, 0)], 1)
 
    elif r[0][0] == '#':
        return -1
    
    else:
        pathfind(0, 0, [(0, 0)], 0)

    if len(paths) == 0:
        return -1

    return paths

原算法性能瓶颈 #

• 回溯法会遍历所有可能路径，20×20迷宫的路径数量是组合数C(38,19)，量级超过10^10，完全无法处理。
• 记录所有路径会占用大量内存，且重复计算同一格子的不同路径状态，效率极低。

优化方案：动态规划（DP） #

由于玩家仅能向右或向下移动，每个格子(i,j)的最少遇怪数仅依赖于上方(i-1,j)和左方(i,j-1)的最少遇怪数，非常适合用动态规划解决。

核心思路 #

1. 构建DP表dp[i][j]：表示从起点(0,0)到(i,j)的最少遇怪数。
2. 初始化：
   • 起点dp[0][0]：若为@则设为1，否则设为0；若为#直接返回-1。
   • 第一行：只能从左方移动而来，若当前格不是墙壁，dp[0][j] = dp[0][j-1] + (1 if r[0][j] == '@' else 0)；若遇墙壁则后续格子不可达，设为无穷大。
   • 第一列：只能从上方移动而来，同理dp[i][0] = dp[i-1][0] + (1 if r[i][0] == '@' else 0)；遇墙壁则后续格子设为无穷大。
3. 状态转移：对于非边界格子(i,j)，若当前格不是墙壁，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + (1 if r[i][j] == '@' else 0)；若为墙壁则设为无穷大。
4. 结果输出：若dp[n-1][n-1]为无穷大则无可达路径，返回-1；否则返回该值，若需要具体路径可通过回溯DP表得到。

优化后代码 #

def min_monster_path(r):
    n = len(r)
    INF = float('inf')
    
    # 初始化DP表
    dp = [[INF]*n for _ in range(n)]
    
    # 起点处理
    if r[0][0] == '#':
        return -1
    dp[0][0] = 1 if r[0][0] == '@' else 0
    
    # 填充第一行
    for j in range(1, n):
        if r[0][j] == '#':
            break  # 后续格子不可达，无需继续计算
        dp[0][j] = dp[0][j-1] + (1 if r[0][j] == '@' else 0)
    
    # 填充第一列
    for i in range(1, n):
        if r[i][0] == '#':
            break  # 后续格子不可达，无需继续计算
        dp[i][0] = dp[i-1][0] + (1 if r[i][0] == '@' else 0)
    
    # 填充其他格子
    for i in range(1, n):
        for j in range(1, n):
            if r[i][j] == '#':
                continue
            # 取上方和左方的最小遇怪数，加上当前格的怪物数
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + (1 if r[i][j] == '@' else 0)
    
    # 检查终点是否可达
    if dp[n-1][n-1] == INF:
        return -1
    
    # 回溯获取具体路径（可选）
    path = []
    i, j = n-1, n-1
    while i >= 0 and j >= 0:
        path.append((i, j))
        if i == 0 and j == 0:
            break
        # 优先选择遇怪数更少的方向，若相等可任选
        if i > 0 and dp[i-1][j] <= dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    path.reverse()
    
    return {'min_monsters': dp[n-1][n-1], 'path': path}

性能对比 #

• 原回溯法：时间复杂度O(2^(2n))，20×20迷宫完全无法运行。
• DP优化后：时间复杂度O(n²)，20×20迷宫仅需400次计算，瞬间完成。

额外优化点 #

• 空间优化：由于每个格子仅依赖上方和左方的状态，可将二维DP表压缩为一维数组，空间复杂度从O(n²)降至O(n)。
• 提前终止：在填充边界时遇墙壁直接break，减少不必要的计算。

内容的提问来源于stack exchange，提问作者user16834984