Hello!
Let's say we have a matrix of size N*N filled with arbitrary positive
integers. Now, let's say we would like to move from the upper left
point ([0,0]) to the lower right point [N-1,N-1] moving only down OR
right, so that a path with the minimum sum of elements is created. Ex .
When n= 3
123
456
789
the minimal path sum is 1 + 2 +3 + 6 + 9 = 21
Now I wrote a recursive function, that calculates the minimal path sum
for a matrix N=80 :
=========================
unsigned long long sum(int i, int j) {
unsigned long long left,right;
if (i == 79 && j == 79) {
return matrix[i][j];
} else if (j == 79 && i != 79) {
return matrix[i][j] + sum(i+1,j);
} else if (i == 79 && j != 79) {
return matrix[i][j] + sum(i, j+1);
}
left = sum(i, j+1);
right = sum(i+1, j);
if (left > right)
return matrix[i][j] + right;
else
return matrix[i][j] + left;
}
=========================
Now, the code works pretty fast for small matrices, but it's running
since last night on the mentioned matrix of size 80*80.The number of
paths it has to check is :
92045125813734238026462263037378063990076729140
so there should be a faster method to determine which path to take. The
only optimisation I can think of is to calculate a "middle bound" and
return a sentinel value as soon as the sum exceeds this value to
indicate that the chosen path isn't optimal. I'm not really sure how to
implement that option (or, if it' possible) so I'm referring to the
list for _any_ code/algorithm optimisation hints.
Thanks.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
