我正在尝试用Python编写一个算法,它可以计算并存储n×m网格中所有可能路径的最大位移。没有障碍。我们从原点开始,每次可以向上或向右移动一个单位长度的网格。对于每个路径,我计算最大位移(使用预定义的公式),然后将该位移附加到列表中,以便在程序完成后可以访问它
我可以毫无问题地计算每条路径的最大位移,并且我已经实现了我的解决方案,这样只保存计算结果,因为没有这个,RAM就会过载。当网格大小为10乘10时,它似乎工作得很好。但是,当我考虑更大的网格(例如30乘30)时,由于要创建大量的路径,计算将花费很长时间。我使用的代码如下
# This function creates the initial path list and calls the function
# to create all possible paths
def findPaths(startRow,startCol,endRow,endCol):
path = [0 for d in range(endRow+endCol-startRow-startCol-1)]
findPathsUtil(endRow,endCol,startRow,startCol,path,0)
# This function is called iteratively until either of the if conditions are met
def findPathsUtil(endRow,endCol,currRow,currCol,path,indx):
global count_global
# If we reach the bottom of maze, we can only move right
if currRow==(endRow-1):
# Completes the remainder of the path until it hits the end point
for k in range(currCol,endCol):
path[indx+k-currCol] = (currRow,k)
# Calculates the maximum displacement for the current path
D_curr = max([abs( elem[1]/endCol - elem[0]/endRow ) for elem in path])
# Append this new displacement to a list of all other found displacements
D_list.append(D_curr)
return
# If we reach to the right most corner, we can only move down
if currCol == (endCol-1):
# Completes the remainder of the path until it hits the end point
for k in range(currRow,endRow):
path[indx+k-currRow] = (k,currCol)
# Calculates the maximum displacement for the current path
D_curr = max([abs( elem[1]/endCol - elem[0]/endRow ) for elem in path])
# Append this new displacement to a list of all other found displacements
D_list.append(D_curr)
return
# This is activated any time we have not yet hit one of the walls
else:
# add Current coordinate to the path list
path[indx]=(currRow,currCol)
findPathsUtil(endRow, endCol, currRow+1, currCol, path, indx+1)
findPathsUtil(endRow, endCol, currRow, currCol+1, path, indx+1)
if __name__ == '__main__':
# Initialize cell array to consider
startRow = 0
startCol = 0
endRow = 3
endCol = 3
global D_list
D_list = []
# First find all displacements for all possible paths are store in global variable D_list
findPaths(startRow,startCol,endRow+1,endCol+1)
我知道一个30乘30的网格有大量与之相关联的可能路径,但是考虑到所有的事情,有些程序认为网格要大得多。有没有什么方法可以大大降低这种计算的时间复杂度?如有任何想法或建议,我们将不胜感激
目前没有回答
相关问题 更多 >
编程相关推荐