The task.

Given a rectangular field D of the size (N, M) of cells (two-dimensional array). Each cell is written a number - the weight of the cell. From the cell (a, b) one can get into the cells (a + 1, b), (a, b + 1) or (a + 1, b + 1). You need to get from the cell (0, 0) into the cell (N - 1, M - 1). The route weight is calculated as the sum of the weights of the cells visited. Find the weight of the minimum route from (0, 0) to (N - 1, M - 1). In short, here is the formula:

G(0, 0) = D[0, 0] G(i, 0) = G(i - 1, 0) + D[i, 0], i > 0 G(0, j) = G(0, j - 1) + D[0, j], j > 0 G(i, j) = min(G(i - 1, j - 1), G(i - 1, j), G(i, j - 1)) + D[i, j], i > 0, j > 0 F(D) = G(N - 1, M - 1)

It’s impossible to write a properly working recursive function that calculates all this. Here is my option, but it is wrong. Where is the mistake? How to be right?

 public static int sum =0; static int G(int i, int j, int[,] D) { if (i == 0 && j == 0) return D[0, 0]; if (j==0&&i!=0) { sum = G(i - 1, 0,D) + D[i, 0]; return G(i - 1, 0, D); } if (i==0&&j!=0) { sum = G(0, j - 1, D) + D[0, j]; return G(0, j - 1, D); } if (i!=0&j!=0) { sum = Math.Min(Math.Min(G(i - 1, j - 1, D), G(i - 1, j, D)), G(i, j - 1, D)) + D[i, j]; return G(i - 1, j - 1, D); } return 1; }

I rewrote the function without the sum, everything is exactly wrong.

  static int G(int i, int j, int[,] D) { if (i == 0 && j == 0) { return D[0, 0]; } if (j==0&&i!=0) { return G(i - 1, 0, D) + D[i, 0]; } if (i==0&&j!=0) { return G(0, j - 1, D) + D[0, j]; } if (i!=0&j!=0) { return Math.Min(Math.Min(G(i - 1, j - 1, D), G(i - 1, j, D)), G(i, j - 1, D)) + D[i, j]; } return 1; }

    3 answers 3

    Well, see for yourself. You have written:

    G (i, 0) = G (i - 1, 0) + D [i, 0], i> 0

    And what about the code?

     if (j==0&&i!=0) { sum = G(i - 1, 0,D) + D[i, 0]; return G(i - 1, 0, D); }

    Why do you need sum and what do you return?

    Update

    You are trying to not optimize something. The fact is that with a recursive call, you will see the same cell many times, and some of the cells you scan will not be included in the final amount. So it is not clear what you think.

    @Valeriy Karchov : The algorithm seems to be correct, in theory the standard application of dynamic programming.

    If we discard the last movement from the optimal path to the cell [i, j] , then we will obviously get the optimal path to the penultimate cell. Since this cell is either [i-1, j] , or [i, j-1] , or [i-1, j-1] , then choosing the optimal path to the cell [i, j] comes down to choosing from three options ( min(G(i - 1, j - 1), G(i - 1, j), G(i, j - 1)) + D[i, j] ).

    It seems all right?

    • Sum to store the amount of weights of the cells visited. And in the code I try to count the visited cells with G (i, 0). - vados
    • @VladD, but it seems to me that the algorithm proposed by @vados does not always return the minimum path, for example, for such an array: 0 4 1 9 9 3 7 7 1 9 3 7 7 4 9 9 3 3 2 9 9 9 9 9 - Valeriy Karchov
    • The algorithm is all right, as it is given in the tasks. The problem with writing a recursive function for this algorithm. - vados
    • @VladD, yes, that's right, thanks for the clarification. - Valeriy Karchov

    Yes, write the usual UCS search in the column. The resulting path found by the algorithm will have the least weight.

       using System; static class WeightGrid { private static int weight(int[,] a, int x, int y, int w) { int m = a.GetLength(0); int n = a.GetLength(1); if (x == m && y == n) { return w; } if (x == m || y == n) { return Int32.MaxValue; } w += a[x, y]; return Math.Min(weight(a, x + 1, y, w), Math.Min(weight(a, x, y + 1, w), weight(a, x + 1, y + 1, w))); } public static void Main(string[] args) { int[,] a = { { 0, 4, 1, 9, 9 }, { 3, 7, 7, 1, 9 }, { 3, 7, 7, 4, 9 }, { 9, 3, 3, 2, 9 }, { 9, 9, 9, 9, 9 } }; Console.WriteLine(weight(a, 0, 0, 0)); } }