Styjun

I am trying to write an algorithm in Python which can calculate and store the maximum displacement for all possible paths in an n by m grid. There is no obstacle. We start at the origin and can travel either upwards or to the right by one unit length of the grid each time. For each path I calculate the maximum displacement (using a predefined formula), and that displacement is then appended to a list so it can be accessed after the program completes.

I can calculate the maximum displacement for each path without a problem, and I have implemented my solution such that only the result of the calculation is saved, as without this the RAM was being overloaded. It appears to work just fine with a grid size of 10 by 10. However, when I consider a larger grid, such as 30 by 30, the calculation will take an intractable time as there are an enormous number of paths to create. The code I am using is below.

# 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)

I understand that a 30 by 30 grid has an incredibly large number of possible paths associated with it, but all things considered there are programs which consider grids much much larger. Is there any way to drastically reduce the time complexity of this calculation? Any thoughts or advice would be highly appreciated.