How do you find the best path in a grid or matrix of dimensions MxN?

I've been asked to find a path to collect the maximum value travelling across a grid. We've been told to start in the bottom left, and end in the top right of the grid.

I haven't got much of a clue as to how I can do this as I'm not too familiar with most of MATLAB's functions and can't seem to find anything that's already been asked to help me.

We've been given the parameter that they are only able to move to the right or up in the grid, and not diagonally, and have to display the path taken and total number of the maximum value.

The example we've been given is the 3x3 matrix:

[7 4 5

8 6 9

1 2 4]

Which you can easily establish the best path to take is 1:8:6:9:5, but I can't quite figure out how to do it aside from writing a code that contains a separate equation for each individual path, and doesn't translate/can't be used for matrices of other dimensions.

Any help at all would be greatly appreciated, even just a place to start or look in order to find what I need.

Answer 1

[Jon]

You should be able to write a recursive function to do this.

The function would provide the next row and column to move to given the current row and column and an array to record which rows and columns you have already visited.

Given that you are at row i and column j you are restricted to move to row i-1 or column j+1. If row -1 has not been visited go there. That is keep column j and move to row i-1. If it has been visited then keep on the same row and move to the next column (j+1). If both have been visited then go back to the row and column that you came from (you'll have to keep track of that too). At each move to a next location, get the value held in that matrix location and add it to the running sum, continue until you reach the upper right corner. Compare the total to the largest so far and if it is bigger then save the path that got you there and the best value so far.

[Jon]

By the way I think that this problem will grow quite quickly (explode) with the size of the matrix, so it may only be possible to complete in a reasonable time without hitting some memory or recursion limits for "small" matrices

[Jon]

Another approach on this would be to generate all of the possible paths using combinations and permutations and then evaluate them. Here's an article that might help you with this approach https://betterexplained.com/articles/navigate-a-grid-using-combinations-and-permutations/

This article also make the combinatorial explosion quite clear!