Блог

Главная - Вопросы по программированию - Интеграция динамического программирования в рекурсивное решение

Интеграция динамического программирования в рекурсивное решение

#c #performance #recursion #dynamic-programming #memoization

#c #Производительность #рекурсия #динамическое программирование #запоминание

Вопрос:

Я пытаюсь применить динамическое программирование к следующей проблеме:

«Робот расположен в верхнем левом углу сетки m x n. Робот может двигаться только вниз или вправо в любой момент времени. Робот пытается добраться до нижнего правого угла сетки. Сколько существует уникальных путей? «

У меня есть рекурсивное решение для этого, которое, я думаю, работает нормально. Однако это медленно:

 int uniquePaths(int m, int n)
    {
        if (m==1 || n==1)
        {
           return 1;
        }
        else 
        {
            return (uniquePaths(m,n-1) uniquePaths(m-1,n));
        }
    }

Я вижу, что было бы полезно, если бы мы могли сохранять выходные данные вызовов uniquePath, поскольку многие из них будут выполняться более одного раза. Одна из моих идей о том, как этого добиться, — создать массив m x n и сохранить в нем выходные данные. Однако это означало бы, что мне нужно будет ввести массив в мою рекурсивную функцию, и я думаю, что для этой проблемы мне разрешено вводить только два целых числа. Есть ли простой способ применить это?

Комментарии:

1. Вы должны быть в состоянии решить это с помощью комбинаторики. Все пути будут иметь n-1 шаги вправо и m-1 вниз (при m условии, что строки и n столбцы). Общее количество шагов равно m n-2 , и любой выбор m-1 из этих шагов будет уменьшен. Таким образом, количество допустимых путей — это количество способов выбора m-1 m n-2 . (Это будет то же значение, что и количество способов выбора n-1 из m n-2 -за симметрии.)

2. Это происходит медленно, потому что в нем используется рекурсия, которую невозможно оптимизировать. Вместо этого используйте цикл.

3. Хорошо, я попробую как цикл, так и комбинаторный маршрут. Что делает рекурсию невозможной для оптимизации?

4. Компилятор обычно может развернуть рекурсию, только если это так называемый «хвостовой вызов», то есть в идеале должен быть только один рекурсивный вызов в конце функции. Проверив эту функцию в gcc, она может развернуть ее, но сгенерированный машинный код по-прежнему ужасен. clang не удается развернуть его. И именно поэтому мы не должны преподавать рекурсию в школе.

5. Добро пожаловать в SO! Возможно, вам будет интересно ознакомиться с потоками решения для projecteuler.net/problem=15 или leetcode.com/problems/unique-paths/description .

Ответ №1:

Вам не нужно вводить массив в качестве аргумента функции. Это может быть локальная переменная.

Наивный способ: использование рекурсивной функции

Если вы действительно хотите использовать рекурсивную функцию, вы можете объявить массив в uniquePaths , затем вызвать другую функцию, которая будет использовать массив и выполнять вычисления.

 int uniquePaths_helper(int *grid, int m, int n, int i, int j);

int uniquePaths(int m, int n)
{
    int *grid = malloc(m * n * sizeof(int));
    int k;
    for (k = 0; k < m * n;   k)
    {
        grid[k] = 0;
    }
    return uniquePaths_helper(grid, 0, 0, m, n);
}

int uniquePaths_helper(int *grid, int m, int n, int i, int j)
{
    if (grid[i * m   j] == 0)
    {
        if (i == n - 1 || j == n - 1)
        {
           grid[i * m   j] = 1;
        }
        else 
        {
            grid[i * m   j] = (
                uniquePaths_helper(grid,m,n, i 1, j)
                  uniquePaths_helper(grid,m,n, i, j 1)
            );
        }
    }
    return grid[i * m   j];
}

Быть умнее: заполнение массива в правильном порядке

В предыдущем решении было много накладных расходов, потому что нам приходилось инициализировать массив значениями по умолчанию, а затем при каждом рекурсивном вызове нам нужно проверять, сохранено ли значение уже в массиве или его нужно вычислить.

Вы можете сократить все это. Заполните массив непосредственно, используя вашу формулу, в ячейках grid , а не в аргументах рекурсивных вызовов.

Формула такова: grid[i * m j] == grid[(i 1) * m j] grid[i * m j 1] .

Единственная сложная часть — выяснить, в каком порядке заполнять массив, чтобы эту формулу можно было записать как простое присваивание, заменив == на = .

Поскольку значение в ячейке зависит только от значений с более высокими i j индексами и, мы можем просто заполнить массив в обратном направлении:

 int uniquePaths(int m, int n)
{
    int *grid = malloc(m * n * sizeof(int));
    int i,j;

    for (int i = 0; i < n;   i)
        grid[i * m   m-1] = 1;
    for (int j = 0; j < m;   j)
        grid[(n-1) * m   j] = 1;

    for (i = n - 2; i >= 0; --i)
    {
        for (j = m - 2; j >= 0; --j)
        {
            grid[i * m   j] = grid[(i 1) * m   j]   grid[i * m   j 1];
        }
    }
    return grid[0];
}