加速以下功能

Question

我正在实现一个代码来查找n*m矩阵中从左上到右下的所有路径

这是我的密码：

# Python3 program to Print all possible paths from
# top left to bottom right of a mXn matrix

'''
/* mat: Pointer to the starting of mXn matrix
i, j: Current position of the robot 
    (For the first call use 0, 0)
m, n: Dimentions of given the matrix
pi: Next index to be filed in path array
*path[0..pi-1]: The path traversed by robot till now 
                (Array to hold the path need to have 
                space for at least m+n elements) */
'''
def printAllPathsUtil(mat, i, j, m, n, path, pi):

    # Reached the bottom of the matrix 
    # so we are left with only option to move right
    if (i == m - 1):
        for k in range(j, n):
            path[pi + k - j] = mat[i][k]

        for l in range(pi + n - j):
            print(path[l], end = " ")
        print()
        return

    # Reached the right corner of the matrix 
    # we are left with only the downward movement.
    if (j == n - 1):

        for k in range(i, m):
            path[pi + k - i] = mat[k][j]

        for l in range(pi + m - i):
            print(path[l], end = " ")
        print()
        return

    # Add the current cell 
    # to the path being generated
    path[pi] = mat[i][j]

    # Print all the paths 
    # that are possible after moving down
    printAllPathsUtil(mat, i + 1, j, m, n, path, pi + 1)

    # Print all the paths 
    # that are possible after moving right
    printAllPathsUtil(mat, i, j + 1, m, n, path, pi + 1)

    # Print all the paths 
    # that are possible after moving diagonal
    # printAllPathsUtil(mat, i+1, j+1, m, n, path, pi + 1);

# The main function that prints all paths 
# from top left to bottom right 
# in a matrix 'mat' of size mXn
def printAllPaths(mat, m, n):

    path = [0 for i in range(m + n)]
    printAllPathsUtil(mat, 0, 0, m, n, path, 0)



def printAllPaths(mat, m, n):
 
    path = [0 for i in range(m + n)]
    printAllPathsUtil(mat, 0, 0, m, n, path, 0)

matrix = np.random.rand(150, 150)
printAllPaths(matrix, 150, 150)

我想找到150×150矩阵的所有路径。但这需要很多时间。有没有一个好办法让它更快？如果还有任何加速算法的建议，那就太好了

Answer 1

我认为当你谈论路径时，一个图是一个很好的解决方案，我的想法是建立一个包含所有路径的图，并要求他给出解决方案，这打印出所有路径，每个节点是坐标（x，y）的对：

import networkx as nx
X = Y = 150

G = nx.DiGraph()
edges = []

for x in range(X):
    for y in range(Y):
        if x<X-1:
            edges.append(((x,y),(x+1,y)))
        if y<Y-1:
            edges.append(((x,y),(x,y+1)))
        
G.add_edges_from(edges)

print(len(G.nodes()))
print(len(G.edges()))

for path in nx.all_simple_paths(G,(0,0),(X-1,Y-1)):
  print(path)