Рубрики

Свойство перекрывающихся подзадач в динамическом программировании | DP-1

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

В этом посте мы подробно обсудим первое свойство (перекрывающиеся подзадачи). Второе свойство динамического программирования обсуждается в следующем посте, т.е. в наборе 2 .

1) Перекрывающиеся подзадачи
2) Оптимальная субструктура

1) Перекрывающиеся подзадачи:
Как и «Разделяй и властвуй», динамическое программирование сочетает в себе решения подзадач. Динамическое программирование в основном используется, когда решения одних и тех же подзадач необходимы снова и снова. В динамическом программировании вычисленные решения подзадач хранятся в таблице, поэтому их не нужно пересчитывать. Таким образом, динамическое программирование бесполезно, когда нет общих (перекрывающихся) подзадач, поскольку нет смысла хранить решения, если они больше не нужны. Например, бинарный поиск не имеет общих подзадач. Если мы возьмем пример следующей рекурсивной программы для чисел Фибоначчи, есть много подзадач, которые решаются снова и снова.

/ * простая рекурсивная программа для чисел Фибоначчи * /

int fib(int n)

{

   if ( n <= 1 )

      return n;

   return fib(n-1) + fib(n-2);

}

Дерево рекурсии для исполнения fib (5)

                              
                         fib(5)
                     /             \
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

Видно, что функция fib (3) вызывается 2 раза. Если бы мы сохранили значение fib (3), то вместо того, чтобы вычислять его снова, мы могли бы повторно использовать старое сохраненное значение. Существует два различных способа хранения значений, чтобы эти значения можно было использовать повторно:
а) памятка (сверху вниз)
б) Табулирование (снизу вверх)

а) Заметки (сверху вниз): запомнившаяся программа для проблемы похожа на рекурсивную версию с небольшой модификацией, которую она просматривает в справочной таблице перед вычислением решений. Мы инициализируем массив поиска со всеми начальными значениями как NIL. Всякий раз, когда нам нужно решение подзадачи, мы сначала изучаем таблицу поиска. Если есть предварительно вычисленное значение, то мы возвращаем это значение, в противном случае мы вычисляем значение и помещаем результат в таблицу поиска, чтобы его можно было использовать позже.

Ниже приводится памятная версия для n-го числа Фибоначчи.

C ++

/ * C ++ программа для Memoized версии
для n-го числа Фибоначчи * /
#include <bits/stdc++.h>

using namespace std;

#define NIL -1 
#define MAX 100 

  

int lookup[MAX]; 

  
/ * Функция для инициализации NIL
значения в справочной таблице * /

void _initialize() 

    int i; 

    for (i = 0; i < MAX; i++) 

        lookup[i] = NIL; 

  
/ * функция для n-го числа Фибоначчи * /

int fib(int n) 

    if (lookup[n] == NIL) 

    

        if (n <= 1) 

            lookup[n] = n; 

        else

            lookup[n] = fib(n - 1) + fib(n - 2); 

  

return lookup[n]; 

  
// Код драйвера

int main () 

    int n = 40; 

    _initialize(); 

    cout << "Fibonacci number is " << fib(n); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

/ * C-программа для Memoized-версии для n-го числа Фибоначчи * /
#include<stdio.h>
#define NIL -1
#define MAX 100

  

int lookup[MAX];

  
/ * Функция для инициализации значений NIL в справочной таблице * /

void _initialize()

{

  int i;

  for (i = 0; i < MAX; i++)

    lookup[i] = NIL;

}

  
/ * функция для n-го числа Фибоначчи * /

int fib(int n)

{

   if (lookup[n] == NIL)

   {

      if (n <= 1)

         lookup[n] = n;

      else

         lookup[n] = fib(n-1) + fib(n-2);

   }

  

   return lookup[n];

}

  

int main ()

{

  int n = 40;

  _initialize();

  printf("Fibonacci number is %d ", fib(n));

  return 0;

}

Джава

/ * Java-программа для Memoized версии * /

public class Fibonacci

{

  final int MAX = 100;

  final int NIL = -1;

  

  int lookup[] = new int[MAX];

  

  / * Функция для инициализации значений NIL в справочной таблице * /

  void _initialize()

  {

    for (int i = 0; i < MAX; i++)

        lookup[i] = NIL;

  }

  

  / * функция для n-го числа Фибоначчи * /

  int fib(int n)

  {

    if (lookup[n] == NIL)

    {

      if (n <= 1)

          lookup[n] = n;

      else

          lookup[n] = fib(n-1) + fib(n-2);

    }

    return lookup[n];

  }

  

  public static void main(String[] args)

  {

    Fibonacci f = new Fibonacci();

    int n = 40;

    f._initialize();

    System.out.println("Fibonacci number is" + " " + f.fib(n));

  }

  
}
// Этот код предоставлен Сакет Кумар

питон

# Программа Python для Memoized-версии n-го числа Фибоначчи

  
# Функция для вычисления n-го числа Фибоначчи

def fib(n, lookup):

  

    # Базовый вариант

    if n == 0 or n == 1 :

        lookup[n] = n

  

    # Если значение не рассчитано ранее, рассчитайте его

    if lookup[n] is None:

        lookup[n] = fib(n-1 , lookup)  + fib(n-2 , lookup) 

  

    # вернуть значение, соответствующее этому значению n

    return lookup[n]

# конец функции

  
# Драйвер программы для проверки вышеуказанной функции

def main():

    n = 34 

    # Объявление таблицы поиска

    # Обрабатывает до n = 100

    lookup = [None]*(101)

    print "Fibonacci Number is ", fib(n, lookup)

  

if __name__=="__main__":

    main()

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для памятной версии n-го числа Фибоначчи

using System;

  

class GFG

{

      

    static int MAX = 100;

    static int NIL = -1;

    static int []lookup = new int[MAX];

      

    / * Функция для инициализации NIL

    значения в справочной таблице * /

    static void initialize()

    {

        for (int i = 0; i < MAX; i++)

            lookup[i] = NIL;

    }

      

    / * функция для n-го числа Фибоначчи * /

    static int fib(int n)

    {

        if (lookup[n] == NIL)

        {

        if (n <= 1)

            lookup[n] = n;

        else

            lookup[n] = fib(n - 1) + fib(n - 2);

        }

        return lookup[n];

    }

      

    // Код драйвера

    public static void Main()

    {

      

        int n = 40;

        initialize();

        Console.Write("Fibonacci number is" + " " + fib(n));

    }

}

  
// Этот код предоставлен Sam007

б) Табулирование (снизу вверх). Табулированная программа для данной проблемы создает таблицу снизу вверх и возвращает последнюю запись из таблицы. Например, для того же числа Фибоначчи мы сначала вычисляем fib (0), затем fib (1), затем fib (2), затем fib (3) и так далее. Так что буквально мы строим решения подзадач снизу вверх.

Ниже приведена табличная версия для n-го числа Фибоначчи.

C / C ++

/ * C программа для Табулированной версии * /
#include<stdio.h>

int fib(int n)

{

  int f[n+1];

  int i;

  f[0] = 0;   f[1] = 1; 

  for (i = 2; i <= n; i++)

      f[i] = f[i-1] + f[i-2];

  

  return f[n];

}

   

int main ()

{

  int n = 9;

  printf("Fibonacci number is %d ", fib(n));

  return 0;

}

Джава

/ * Java-программа для Табулированной версии * /

public class Fibonacci

{

  int fib(int n)

  {

    int f[] = new int[n+1];

    f[0] = 0;

    f[1] = 1;

    for (int i = 2; i <= n; i++)

          f[i] = f[i-1] + f[i-2];

    return f[n];

  }

  

  public static void main(String[] args)

  {

    Fibonacci f = new Fibonacci();

    int n = 9;

    System.out.println("Fibonacci number is" + " " + f.fib(n));

  }

  
}
// Этот код предоставлен Сакет Кумар

питон

# Python-программа Табулированная (снизу вверх) версия

def fib(n):

  

    # объявление массива

    f = [0]*(n+1)

  

    # базовое назначение

    f[1] = 1

  

    # вычисление Фибоначчи и сохранение значений

    for i in xrange(2 , n+1):

        f[i] = f[i-1] + f[i-2]

    return f[n]

  
# Драйвер программы для проверки вышеуказанной функции

def main():

    n = 9

    print "Fibonacci number is " , fib(n)

  

if __name__=="__main__":

    main()

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для табличной версии

using System;

  

class GFG

{

    static int fib(int n)

    {

        int []f = new int[n + 1];

        f[0] = 0;

        f[1] = 1;

        for (int i = 2; i <= n; i++)

            f[i] = f[i - 1] + f[i - 2];

        return f[n];

    }

      

    public static void Main()

    {

          

        int n = 9;

        Console.Write("Fibonacci number is" + " " + fib(n));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP-программа для табличной версии

  

function fib($n)

{

    $f[$n + 1]=0;

    $i;

    $f[0] = 0;

    $f[1] = 1; 

    for ($i = 2; $i <= $n; $i++)

        $f[$i] = $f[$i - 1] + 

                 $f[$i - 2];

      

    return $f[$n];

}

  
// Код драйвера

$n = 9;

echo("Fibonacci number is "); 

echo(fib($n));

  
// Этот код предоставлен нитин митталь.
?>


Выход:

 Fibonacci number is 34

Как в Таблице, так и в Записках хранятся решения подзадач. В Memoized версии таблица заполняется по требованию, а в табличной версии, начиная с первой записи, все записи заполняются одна за другой. В отличие от табличной версии, все записи таблицы поиска не обязательно заполняются в Memoized-версии. Например, мемоизированное решение проблемы LCS не обязательно заполняет все записи.

Чтобы увидеть оптимизацию, достигнутую с помощью мемоизированных и табличных решений по сравнению с базовым рекурсивным решением, посмотрите время, затраченное на следующие прогоны для вычисления 40-го числа Фибоначчи:

Рекурсивное решение
Мемоизированное решение
Табличное решение

Время, затрачиваемое методом рекурсии, намного больше, чем два метода динамического программирования, упомянутые выше — памятка и табуляция!

Кроме того, см. Метод 2 публикации « Гадкий номер» для еще одного простого примера, где у нас есть перекрывающиеся подзадачи, и мы храним результаты подзадач.

Мы рассмотрим Оптимальное свойство подструктуры и еще несколько примеров проблем в будущих статьях по динамическому программированию.

Попробуйте следующие вопросы в качестве упражнения этого поста.
1) Напишите мемоизированное решение для проблемы LCS. Обратите внимание, что табличное решение приведено в книге CLRS.
2) Как бы вы выбрали между Memoization и Tabulation?

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Ссылки:
http://www.youtube.com/watch?v=V5hZoJ6uK-s

Рекомендуемые посты:

Свойство перекрывающихся подзадач в динамическом программировании | DP-1

0.00 (0%) 0 votes