Path combination across matrix

10 次查看（过去 30 天）
L. Edwin M.
L. Edwin M. 2022-3-7
评论： L. Edwin M. 2022-3-8
Hello! I am new to Matlab and need your help!
I would like to find two paths across a matrix with elements of 0, 1 and 2. So it is like you walk from the first row to the last row and you are only allowed to walk forward and not backward or sideward in the same row and you have to avoid 0 except there is a row filled only with 0. At the end I would like to have a "path vector" with the column index of the path and the sum of the elements collected on the path through the matrix. (example below the code)
The first case is the path with the maximum sum. If there are more solutions with the same max sum it should be the path with the max sum and the minimum of column variation.
In the second case the prios change, so the path should be the path with the minimum of column variation and if there are more solutions it should be the path with minimum of column variation and max sum.
As a result of my first try i get a matrix and every row is one possible path. Next step is to sort the matrix last column so i get the max sum and thus the "best path". Works good for a small matrix but my matrix is about 60x10 so i would need a lot of "for" loops..any solutions for this?
And i have no clue how to get solved my second case with minimum of varitations so the max of same column indices.
A = [2 1 0 1;
2 1 2 0;
0 2 0 1];
z=1;
for j=1:4
if A(1,j)>0
for g=1:4
if A(2,g)>0
for h=1:4
if A(3,h)>0
Z(z,1)=[j];
Z(z,2)=[g];
Z(z,3)=[h];
Z(z,4)=[A(1,j)+A(2,g)+A(3,h)];
z=z+1;
end
end
end
end
end
end
  1. Case "max sum" solution vector: [1 1 2 6] -> first row 1 column, second row 1 column, third row 2 column -> sum 2+2+2=6
  2. In the case that f.e. second row is filled with 0 it should be f.e. [1 0 1 2 6]
  3. Second case "minimum variations" solution vector: [2 2 2 4]
Many thanks!!!

请先登录，再回答此问题。

回答（1 个）

Image Analyst
Image Analyst 2022-3-7
See Steve's blog series on the shortest path. You could probably adapt that to your situation:
Exploring shortest paths – bwdistgeodesic
Otherwise look to A* or dynamic programming.
  3 个评论
显示 1更早的评论
Image Analyst
Image Analyst 2022-3-8
I believe the way to solve it is with dynamic programming:
https://en.wikipedia.org/wiki/Dynamic_programming
Basically you have two matrices the same size as your input matrix. One holds the cumulative sums and one holds the directions that the path came from. I was working on a demo but it's not finished yet and I don't know when it will be.
L. Edwin M.
L. Edwin M. 2022-3-8
Do you think i could also solve at least the max sum case with the code below?
So my Matrix M contains the indices of rows and columns of the max values of A. In row 2 i have two path solutions because of the two 2, also in row 3 i have two path possibilities.
How can i get all column indices of one row in one vector, as in the next step i want to combine all three vectors to get my path possibilities in a matrix?
Required example output matrix: [1 1 2; 1 1 4; 1 3 1; 1 3 4]
A = [2 1 0 1; 2 1 2 0; 0 1 0 1];
V = max(A,[],2);
idx_max = A==V;
[row, col] = find(idx_max);
M=[row, col];
M=sortrows(M,1); % -> don't know if needed
%column indices of max values of the same row in one vector -> v1, v2, v3
%all combinations of these vectors in the order v1 -> v2 -> v3 --> all possible paths

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Creating and Concatenating Matrices 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by