Prim算法生成迷宫的优先向东回溯求解算法失效，求问题排查方法

核心错误点 #

• 方向移动函数坐标判断逻辑错误
  四个Vers_*方向函数中，误将当前坐标(i,j)作为可通行判断对象，实际应该判断目标方向的坐标是否为通路（值为0）。以Vers_Est为例，原代码判断laby[i][j] == 0，正确应为laby[i][j+1] == 0。
• 移动后未更新当前坐标
  backtracking函数中调用方向移动函数后，未更新当前坐标i、j为移动后的新坐标，导致每次循环都在原位置重复判断，陷入死循环。
• 回溯函数语法错误
  四个Demi_tour_*回溯函数中，移除路径点的写法错误，P.remove[(i,j)]应为P.remove((i,j))，且回溯后同样需要更新当前坐标为路径的最后一个点。
• 循环终止条件错误
  原终止条件M[i][j] != M[X-2][Y-1]逻辑不成立：出口坐标的值为0，而你会将走到的坐标标记为0.5，永远不会匹配，应直接判断当前坐标是否等于出口坐标(i,j) != (X-2, Y-1)。
• 参数传递错误
  Prim函数返回值为三元组(迷宫矩阵, 起点, V)，调用backtracking时直接传入了整个三元组，应只传入迷宫矩阵Prim(3,3)[0]。
• 冗余调用与笔误
  initialisation被重复调用两次，无需重复执行；Vers_Sud调用行末尾多写了[0]，导致移动逻辑未正确执行。

修正后核心代码示例 #

修正后的方向移动函数 #

def Vers_Est(laby, i, j, P):
    # 改为判断东侧目标坐标是否为通路
    if j+1 < laby.shape[1] and laby[i][j+1] == 0:
        P.append((i,j+1))
        laby[i][j+1] = 0.5
        # 返回新的坐标
        return True, laby, P, i, j+1
    else :
        return False, laby, P, i, j

# 其余三个方向函数同理修改，分别判断对应方向的目标坐标，返回正确的新坐标
def Vers_Ouest(laby, i, j, P):
    if j-1 >= 0 and laby[i][j-1] == 0:
        P.append((i,j-1))
        laby[i][j-1] = 0.5
        return True, laby, P, i, j-1
    else :
        return False, laby, P, i, j

def Vers_Sud(laby, i, j, P):
    if i+1 < laby.shape[0] and laby[i+1][j] == 0:
        P.append((i+1,j))
        laby[i+1][j] = 0.5
        return True, laby, P, i+1, j
    else :
        return False, laby, P, i, j

def Vers_Nord(laby, i, j, P):
    if i-1 >=0 and laby[i-1][j] == 0:
        P.append((i-1,j))
        laby[i-1][j] = 0.5
        return True, laby, P, i-1, j
    else :
        return False, laby, P, i, j

修正后的回溯逻辑与主求解函数 #

def backtracking(laby):
    M, P = initialisation(laby)
    i, j = 0, 1
    X, Y = M.shape
    exit_pos = (X-2, Y-1)
    # 终止条件改为坐标匹配
    while (i,j) != exit_pos :
        moved = False
        # 按优先级判断四个方向，移动后更新i,j
        moved, M, P, i, j = Vers_Est(M, i, j, P)
        if moved:
            continue
        moved, M, P, i, j = Vers_Sud(M, i, j, P)
        if moved:
            continue
        moved, M, P, i, j = Vers_Ouest(M, i, j, P)
        if moved:
            continue
        moved, M, P, i, j = Vers_Nord(M, i, j, P)
        if moved:
            continue
        # 四个方向都走不通则回溯
        M[i][j] = 0.2
        P.pop()
        i, j = P[-1]
    return M, P

# 调用时传入Prim返回的迷宫矩阵
print(backtracking(Prim(3,3)[0]))

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