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

Janne Karila · Accepted Answer · 2014-12-04 20:01:06Z

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.

Stack Exchange Network

Memoization for calculating minimal traversal distance within a positive matrix

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Memoization for calculating minimal traversal distance within a positive matrix

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions