0

Задание.

Дано прямоугольное поле D размером (N, M) клеток (двумерный массив). В каждой клетке написано число – вес клетки. Из клетки (a, b) можно попасть в клетки (a + 1, b), (a, b + 1) или (a + 1, b + 1). Вам надо попасть из клетки (0, 0) в клетку (N – 1, M – 1). Вес маршрута вычисляется как сумма весов посещенных клеток. Найдите вес минимального маршрута из (0, 0) в (N – 1, M – 1). Короче, вот формула:

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)

Никак не получается написать правильно работающую рекурсивную функцию которая это все вычисляет. Вот мой вариант, но считает неверно. В чем ошибка? Как будет правильно?

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;

    }

Переписал функцию без суммы, все ровно считает неправильно.

        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 ответа 3

1

Ну смотрите сами. У вас написано:

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

А что в коде?

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

Для чего вам sum и что вы возвращаете?

Обновление

Вы пытаетесь что-то не то соптимизировать. Дело в том, что при рекурсивном вызове у вас одна и та же клетка будет просматриваться много раз, а некоторые просмотренные клетки не войдут в финальную сумму. Так что непонятно, что вы считаете.

@Valeriy Karchov: Алгоритм кажется правильным, по идее стандартное применение динамического программирования.

Если отбросить от оптимального пути в клетку [i, j] последнее движение, то получится очевидно оптимальный путь в предпоследнюю клетку. Поскольку эта клетка либо [i-1, j], либо [i, j-1], либо [i-1, j-1], то выбрать оптимальный путь в клетку [i, j] сводится к выбору из трёх вариантов (min(G(i - 1, j - 1), G(i - 1, j), G(i, j - 1)) + D[i, j]).

Вроде всё верно?

4
  • Sum для хранения суммы весов посещенных клеток. А в коде я пытаюсь считать посещенные клетки при G(i,0).
    – vados
    25 фев 2015 в 15:23
  • @VladD, а мне вот кажется, что алгоритм, предложенный @vados, не всегда возвратит минимальный путь, например, для такого массива: 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 25 фев 2015 в 15:26
  • В алгоритме все верно, так как он дан в заданий. Проблема с написанием рекурсивной функции по этому алгоритму.
    – vados
    25 фев 2015 в 15:58
  • @VladD, да, всё верно, спасибо за разъяснение. 25 фев 2015 в 15:58
0

Да напишите обычный UCS поиск в графе. Результирующий путь, найденный алгоритмом будет иметь наименьший вес.

0
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));
    }
}

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.