Skip to main content
K
klax9-Granite
9-Granite
August 7, 2017
Question

Matrix path

  • August 7, 2017
  • 4 replies
  • 6806 views

I am trying to work out how to calculate all the paths from each cell in column zero to the end column.

This is part of project to calculate the remaining strength in a material.  The matrix represents a grid on the material.  Each cell in the matrix contains a measured parameter at a location on the grid.

I need to calculate the sum of all the paths available from each of the cells in column zero.  The path can progress one cell up or one cell down or one cell across.  It can never go backwards.

 

In the attached file is a grid of 5 x 7, with fictitious data.  In reality the grids are more likely to be 20 x 40.

 

I can see how to do it manually but I cannot see how to do it within Mathcad.

 

Any direction or guidance would be appreciated.

 

The system will not allow me to attach a file. "The contents of the attachment doesn't match its file type", which is nonsense because it is an mcdx file.

 

 

 

Thank you

4 replies

M
MartinHanak24-Ruby III
24-Ruby III
August 8, 2017

Hi,

 

please explain how do you calculate the sum of all the paths manually.

K
klax9-GraniteAuthor
9-Granite
August 8, 2017

Good Morning Martin,

Thank you for replying to my post.

 

I mapped out the first few rows manually.  For example, if we assume an origin of 1 and the rows labelled A to D and the columns 1 to 7 and we start at cell A1.

 

A1 can go to A2 or B1.  If it goes to A2 then it can go to A3 or B2.  If it goes to A3 then it can go to A4 or B3 etc.

 

A2 can go to A1 A3 and B2 etc.

 

From that you can build up all of the paths possible from A1.  Then you have to move to A2 and repeat the performance.

 

Then you can sum up the value total for each path and perform various calculations on them.

 

I hope that is clear.

 

Kind Regards

W
Werner_E25-Diamond I
25-Diamond I
August 8, 2017

There are still some questions.

1) Is the following correct: We never go to the left and we never go back (up or down) from where we came. That way endless paths are excluded


2) Where does a path end. You wrote that it spans from the first column to the last one.

 

2a) Are we allowed to go up or down when we reach the rightmost column or

 

2b) do we have to stop immediately when we reach the first time a cell in the last column?
In other words: Is C1-C2-C3-B3-B4-B5-B6-B7-C7 a valid path or not?


3) What should the result be? You wrote "I need to calculate the sum of all the paths available from each of the cells in column zero." What means "sum of all the paths"?

3a) Are you just interested in the number of paths possible from each of the cells in the first column. The result being a 5-element vector representing the number of paths for each of the 5 start cells.
This is probably not what you are looking for, as the values in the cells would be irrelevant and the result would be the same for any cell in the first column -> r^(c-1) if you have a r x c matrix.

3b) Do you intend to add all numbers for all paths possible from a start cell? The result being a 5-element vector and each element is the total sum of of all cell values for all paths possible from each of the 5 start cells.

3c) Similar as 3b), but this time the sum of values is listed separately for each path. That way for each start cell we would have a list of results. The result could be either represented by a nested 5-element vector and this time the elements would be vectors again, representing the cell sums of each of the 15625 paths possible from a start cell. Or you could represent the result in a 5 * 15625 matrix.
You will of course loose any information as to which path which value belongs to.
For a 20 x 40 matrix the result would be a matrix with 20 rows and 5.498*10^50 columns!! Guess this is also not what you are looking for, right?

Whatever the result should be - I think that the easiest approach would be a function which is called recursively. There is no easy, ready-made function available you could use out of the box. You will have to use some programming.

I can't read your file with my version of Prime so I can't see if you just provided a 5 x 7 matrix or if you already have tried some approach. You may consider attaching a screenshot or a pdf-print of your file in the latter case.

M
MartinHanak24-Ruby III
24-Ruby III
August 8, 2017

Hi,

 

1.]

If I understand you well, the path can start in any matrix cell. This means in 1,1 an also in 3,7 (for example).

 

2.]

If I understand you well, the path ends in 7th column. This means step from 2,7 to 3,7 is forbidden.

 

3.]

Are you able to create program solving your problem in any programming language ? I mean Basic, C, Pascal, ...

L
LucMeekes23-Emerald IV
23-Emerald IV
August 9, 2017

It appears to me you want to have the path for each route as well.

I made one simplification: starting in the first column, a route can only go left as the first step.

Here is the implementation and some results.

Cracks1.pngCracks2.pngCracks3.pngCracks4.pngCracks5.png

Of course, with the amount of informatioin stored, the maximum array size determines the maximum size of the original matrix that can be processed successfully.

It appears that in Mathcad 11 8x7 is the largest size.

Maybe Prime allows to go further, but (as Werner already observed) there's also a (calculation) time aspect. Time grows exponentially with matrix size.

 

Success!
Luc

L
LucMeekes23-Emerald IV
23-Emerald IV
August 9, 2017

Just a thought...

Would it not be more realistic if the crack direction was (at least partly) chosen by data in the matrix?

I could imagine that a crack route has a preference for the surrounding cell with the smallest (or else the largest) value of the three (up, forward, down) cells. But I have to admit that I have no idea about the actual meaning of the matrix cell values...

But if this knowledge could be used, then a single route would result from each of the starting points, which would not only make the result matrix much shorter, but it would also calculate faster because less paths have to be investigated by the recursive routine.

 

Luc

Terms & ConditionsCookie settingsAccessibility statement