Memoization for calculating minimal traversal distance within a positive matrix

Question

The code below is for calculating the minimal traversing distance from the top left point of the matrix to the bottom right point of the matrix.

GitHub

Here is the core functionality. Please note that y is a global variable keeping track of the memoization.

def findLeastPath(matrix, row=0, column=0, path=[], sum_=0):
 row_max = matrix.shape[0]
 column_max = matrix.shape[1]
 if column == column_max - 1 and row == row_max - 1:
 y[row][column] = matrix[row][column]
 return matrix[row][column] + sum_
 else:
 current_cost = matrix[row][column]
 path.append((row, column, current_cost))
 if column == column_max - 1:
 if y[row+1][column] != 0:
 y[row][column] = current_cost + y[row+1][column]
 return current_cost + y[row+1][column]
 else:
 down = findLeastPath(matrix, row + 1, column, path, sum_ + current_cost)
 y[row][column] = current_cost + y[row+1][column]
 return down
 elif row == row_max - 1:
 if y[row][column+1] != 0:
 y[row][column] = current_cost + y[row][column + 1]
 return current_cost + y[row][column + 1]
 else:
 right = findLeastPath(matrix, row, column + 1, path, sum_ + current_cost)
 y[row][column] = current_cost + y[row][column + 1]
 return right
 else:
 if y[row][column + 1] != 0:
 right = y[row][column + 1] + current_cost
 else:
 findLeastPath(matrix, row, column + 1, path, sum_ + current_cost)
 right = y[row][column + 1] + current_cost
 if y[row + 1][column] != 0:
 down = y[row + 1][column] + current_cost
 else:
 findLeastPath(matrix, row + 1, column, path, sum_ + current_cost)
 down = y[row+1][column] + current_cost
 if y[row + 1][column + 1] != 0:
 diagonal = y[row + 1][column + 1] + current_cost
 else:
 findLeastPath(matrix, row + 1, column + 1, path, sum_ + current_cost)
 diagonal = y[row+1][column+1] + current_cost
 min_val = min(right, down, diagonal)
 y[row][column] = min_val
 return min_val

Answer 1

• Some documentation is sorely needed, both about the problem itself, and the approach taken to solve it.

• Making y global is not a good idea. If you want to solve more than one matrix, the caller of this function would be responsible for resetting y between calls. Instead you could pass y around as an argument, perhaps initializing it like this:

  def findLeastPath(matrix, y=None, row=0, column=0, path=[], sum_=0):
   if y is None:
   y = numpy.zeros_like(matrix)
  

• I see that the possible moves are only right, down and diagonally down-right. The problem could be solved in a simple way by looping once through the array row by row. One can always easily compute the minimum cost of reaching the current node, because it is only possible to arrive from nodes whose cost has already been computed.

• Dijkstra's algorithm is another option if costs are non-negative. Basically, always extend the shortest path by one step. Pro: may not have to visit all the nodes. Con: needs to maintain a priority queue.