基于Python求解N×N矩阵的最低成本路径问题

问题梳理 #

需求：给定N×N的随机整数矩阵（元素值0-9），求从起点(0,0)到终点(N-1,N-1)的最低成本路径，输出路径的坐标元组列表及总成本（路径上所有节点数值之和）。

现有代码的问题 #

1. get_neighbour函数逻辑错误：
   • 遍历整个矩阵寻找与当前节点值相同的位置，完全偏离了“相邻节点”的定义。相邻节点应为当前坐标的上下左右四个方向、且坐标在矩阵范围内的位置，与节点值无关。
2. Tree类实现逻辑混乱：
   • add_children方法中，将邻居列表直接追加到Children，随后把self.value设为该列表，导致类型错误（value应为坐标元组，却变成了列表）。
   • 未正确实现树的层级遍历，无法追踪所有可能路径的成本。

适合的替代解法（无需树结构） #

由于课程尚未讲授树结构，推荐两种更适配的方法：

方法1：动态规划（仅允许向右/向下移动） #

如果题目限定只能向右或向下移动（此类作业的常见设定），动态规划是最简单的解法，时间复杂度为O(N²)。

思路：

• 创建DP矩阵，dp[i][j]表示从(0,0)到(i,j)的最低成本。
• 初始化：dp[0][0] = matrix[0][0]；第一行只能从左侧累加，dp[0][j] = dp[0][j-1] + matrix[0][j]；第一列只能从上方累加，dp[i][0] = dp[i-1][0] + matrix[i][0]。
• 状态转移：对于其他位置，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]，取上方或左侧的最小成本加上当前节点值。
• 回溯路径：从终点(N-1,N-1)反向推导，每次选择成本更小的前驱节点（上方或左侧），直到回到起点，再反转得到正序路径。

代码实现：

import random

def generate_matrix(n):
    return [[random.randint(0, 9) for _ in range(n)] for _ in range(n)]

def find_min_path_dp(matrix):
    n = len(matrix)
    if n == 0:
        return [], 0
    
    # 初始化DP矩阵
    dp = [[0]*n for _ in range(n)]
    dp[0][0] = matrix[0][0]
    
    # 填充第一行
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + matrix[0][j]
    
    # 填充第一列
    for i in range(1, n):
        dp[i][0] = dp[i-1][0] + matrix[i][0]
    
    # 填充其他位置
    for i in range(1, n):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
    
    # 回溯路径
    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:
            j -= 1
        elif j == 0:
            i -= 1
        else:
            if dp[i-1][j] < dp[i][j-1]:
                i -= 1
            else:
                j -= 1
    # 反转得到正序路径
    path.reverse()
    return path, dp[n-1][n-1]

# 测试
n = 5
matrix = generate_matrix(n)
print("生成的矩阵：")
for row in matrix:
    print(row)

path, total_cost = find_min_path_dp(matrix)
print("\n最低成本路径：", path)
print("路径总成本：", total_cost)

方法2：Dijkstra算法（允许任意方向移动） #

如果题目允许上下左右任意移动（可能形成回路），则使用Dijkstra算法，这是解决带权重最短路径问题的经典方法，适配无负权值的场景（矩阵元素均为0-9）。

思路：

• 用优先队列（小顶堆）存储待访问节点，每个元素为(当前总成本, 当前坐标, 路径)。
• 用距离矩阵记录每个坐标的最低成本，初始时仅(0,0)设为matrix[0][0]，其余设为无穷大。
• 每次弹出堆中成本最小的节点，遍历其四个相邻节点，计算新成本；若新成本小于该相邻节点的记录成本，则更新并加入堆。
• 到达终点(N-1,N-1)时，直接返回路径和总成本。

代码实现：

import random
import heapq

def generate_matrix(n):
    return [[random.randint(0, 9) for _ in range(n)] for _ in range(n)]

def find_min_path_dijkstra(matrix):
    n = len(matrix)
    if n == 0:
        return [], 0
    
    # 四个移动方向：上下左右
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    # 距离矩阵，记录每个坐标的最小成本
    dist = [[float('inf')]*n for _ in range(n)]
    dist[0][0] = matrix[0][0]
    
    # 优先队列：(当前总成本, x坐标, y坐标, 路径)
    heap = []
    heapq.heappush(heap, (matrix[0][0], 0, 0, [(0,0)]))
    
    while heap:
        current_cost, x, y, path = heapq.heappop(heap)
        
        # 到达终点，直接返回
        if x == n-1 and y == n-1:
            return path, current_cost
        
        # 如果当前成本大于已知的最小成本，跳过
        if current_cost > dist[x][y]:
            continue
        
        # 遍历四个方向
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n:
                new_cost = current_cost + matrix[nx][ny]
                # 如果新成本更小，更新并加入堆
                if new_cost < dist[nx][ny]:
                    dist[nx][ny] = new_cost
                    new_path = path.copy()
                    new_path.append((nx, ny))
                    heapq.heappush(heap, (new_cost, nx, ny, new_path))
    
    # 理论上不会走到这里，因为总有路径可达
    return [], float('inf')

# 测试
n = 5
matrix = generate_matrix(n)
print("生成的矩阵：")
for row in matrix:
    print(row)

path, total_cost = find_min_path_dijkstra(matrix)
print("\n最低成本路径：", path)
print("路径总成本：", total_cost)

说明 #

• 若作业限定只能向右/向下移动，优先使用动态规划，高效且易理解；若允许任意方向，选择Dijkstra算法。
• 两种方法均无需树结构，符合课程当前进度要求。

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