Help! Matrix minimal path?

I'm very new to Matlab and I am trying to find a way to find the 'minimal sum' with a 'path' that travels from the top left of the matrix to the bottom right while only being able to move in the right and down directions.

any help would be greatly appreciated!

Ex.

131 673 234 103  18
201  96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524  37 331

The path traveled should be: 131, 201, 96, 342, 746, 422, 121, 37, 331. This should then output a sum of 2427.

Thanks!

Answer 1

[Image Analyst]

Looks like a perfect case for dynamic programming ( http://en.wikipedia.org/wiki/Dynamic_programming). I did exactly this for vessel tracking during my dissertation. You could also use A* ( http://en.wikipedia.org/wiki/A*), another favorite of mine.

Answer 2

[Geoff]

The REAL way to do this is to implement Dijkstra's Algorithm: http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Or to use dynamic programming as Image Analyst suggested.

But you could try using a method similar to one I offered in your other question about the matrix max sum http://www.mathworks.com.au/matlabcentral/answers/36233-matrix-max-sum

Here, you want to look at every possible permutation of a move to the right and a move down. You could represent these using 0 and 1...

paths = perms([0 0 0 0 1 1 1 1]);

Unfortunately, perms doesn't recognise that our values are non-unique, so you get thousands of duplicates.

But what if you say "oh this is just binary". So how many bits do we need? Eight. Let's generate them all...

paths = double( dec2bin(0:2^8-1, 8) == '1' );

But we want to throw out anything that doesn't have exactly 4 ones (or zeros)...

paths(sum(paths,2) ~= 4, :) = [];

However it might be useful to note that if you used the number 5 to represent a move to the right, and the number 1 to represent a move down, then you can take advantage of MatLab's column-first linear indexing. Since we already have the ones, let's turn the zeros into a 5:

paths(~paths) = 5;

Don't forget this is for movement: you need to add in the first index. I'll use another 'one':

paths = [ones(size(paths,1),1) paths];

And now the magic:

paths = cumsum(paths,2);

You now have a linear index for every possible path, given your problem constraints. Now work out which one is the best.

For any particular path, p, you can get every visited element in the matrix M by simply stating:

M(p)

The rest is up to you... If I've left you anything to do! =)

[Richard Brown]

But Dijkstra's algorithm *is* dynamic programming :)

Oh how I wish I had ijk in the middle of my name

[Geoff]

Oh! Hehehe. Some computer scientist I turned out to be... =) I learned that algorithm before I learned what dynamic programming is. Actually, the concept still messes with my brain sometimes.