想要算法在 3*3 维的网格中找到最短路径

Question

我需要下图的帮助我想在 Python 中实现以下逻辑，我是 Python 中的新手。

[![我需要下图的帮助我想在 Python 中实现以下逻辑，我是 Python 中的新手。][1]][1]

感谢任何帮助。

Answer 1

我建议寻找所有可能的路径。来自 link 的示例然后计算每个可能的总和并寻找最小的

import numpy as np
import copy

def findPaths(mat, path,paths, i, j):
    # base case
    if not mat or not len(mat):
        return
    (M, N) = (len(mat), len(mat[0]))
    # if the last cell is reached, print the route
    if i == M - 1 and j == N - 1:
        paths.append(copy.deepcopy(path + [[i,j]]    ))
        return
    # include the current cell in the path
    path.append( [i,j])
    # move right
    if 0 <= i < M and 0 <= j + 1 < N:
        findPaths(mat, path,paths, i, j + 1)
    # move down
    if 0 <= i + 1 < M and 0 <= j < N:
        findPaths(mat, path,paths, i + 1, j)
    # backtrack: remove the current cell from the path
    path.pop()


if __name__ == '__main__':
    mat = [ [2,5,4],
            [3,2,1],
            [8,0,3] ]

    path = []
    paths = []
    x = y = 0
    #find all possible paths
    findPaths(mat, path,paths, x, y)
    print(paths)
    #get the sum of all paths
    All_sums = []
    for path in paths:
        one_sum = 0
        for p in path:
            one_sum += mat[p[0]][p[1]]
        All_sums.append(one_sum)
    print(All_sums)
    #get lower path
    min_path = np.argmin(All_sums)
    print(min_path)
    #print the path
    print(paths[min_path])
    #print the val sequence
    print([mat[p[0]][p[1]] for p in paths[min_path]])

Answer 2

我们可以使用递归轻松解决这个问题。这个想法是从矩阵的 top-left 单元格开始，并为下一个节点（紧邻右侧或紧邻底部单元格）重复出现，并继续为每个访问过的单元格执行此操作，直到到达目的地。还维护一个路径数组以存储当前路径中的节点，并在访问任何单元格时更新路径数组（包括当前节点）。现在，每当到达目的地（bottom-right 角）时，打印路径数组。

想要算法在 3*3 维的网格中找到最短路径

Want algorithm to find shortest path in grid which 3*3 dimension

python

python-3.x

dataframe

python-2.7