二维矩阵的最小成本路径

Question

我试图找到从点 (0, 0) 到点 {(u, v) | 的最小成本路径u + v <= 100} 在我生成的二维数据矩阵中。

我的算法非常简单，目前我已经设法产生了以下（可视化）结果，这让我明白我的算法还差得远。

# each cell of path_arr contains a tuple of (i,j) of the next cell in path.
# data contains the "cost" of stepping on its cell
# total_cost_arr is used to assist reconstructing the path.
def min_path(data, m=100, n=100):
    total_cost_arr = np.array([np.array([0 for x in range(0, m)]).astype(float) for x in range(0, n)])
    path_arr = np.array([np.array([(0, 0) for x in range(0, m)], dtype='i,i') for x in range(0, n)])
    total_cost_arr[0, 0] = data[0][0]

    for i in range(0, m):
        total_cost_arr[i, 0] = total_cost_arr[i - 1, 0] + data[i][0]

    for j in range(0, n):
        total_cost_arr[0, j] = total_cost_arr[0, j - 1] + data[0][j]

    for i in range(1, m):
        for j in range(1, n):
            total_cost_arr[i, j] = min(total_cost_arr[i - 1, j - 1], total_cost_arr[i - 1, j], total_cost_arr[i, j - 1]) + data[i][j]
            if total_cost_arr[i, j] == total_cost_arr[i - 1, j - 1] + data[i][j]:
                path_arr[i - 1, j - 1] = (i, j)
            elif total_cost_arr[i, j] == total_cost_arr[i - 1, j] + data[i][j]:
                path_arr[i - 1, j] = (i, j)
            else:
                path_arr[i, j - 1] = (i, j)

path_arr 的每个单元格包含路径中下一个单元格的 (i,j) 元组。 data 包含踩踏其单元格的“成本”，并且 total_cost_arr用于辅助重建路径

我认为将 (i,j) 放在前一个单元格中会引起一些冲突，从而导致这种行为。

Answer 1

我认为数组不是解决您的问题的最佳结构。

你应该使用一些图形数据结构（networkx for example) and use algorithm like the Dijkstra one's or A*（从第一个派生而来）。

Dijkstra 算法在 netwokrkx (function for shortest path) 中实现。

二维矩阵的最小成本路径

Minimal cost path of 2d matrix

python

shortest-path