Propriedade de subproblemas sobrepostos na programação dinâmica

A Programação Dinâmica é um paradigma algorítmico que resolve um determinado problema complexo dividindo-o em subproblemas e armazena os resultados dos subproblemas para evitar computar os mesmos resultados novamente. A seguir estão as duas propriedades principais de um problema que sugere que o problema determinado pode ser resolvido usando a programação dinâmica.

Nesta postagem, discutiremos a primeira propriedade (Subproblemas de sobreposição) em detalhes. A segunda propriedade da programação dinâmica é discutida no próximo post, ou seja, o Conjunto 2 .
1) Subproblemas de sobreposição
2) Subestrutura ótima

1) Subproblemas sobrepostos:
Como Dividir e Conquistar, a Programação Dinâmica combina soluções para subproblemas. A Programação Dinâmica é usada principalmente quando as soluções dos mesmos subproblemas são necessárias repetidamente. Na programação dinâmica, as soluções computadas para os subproblemas são armazenadas em uma tabela para que não precisem ser recalculadas. Portanto, a Programação Dinâmica não é útil quando não há subproblemas comuns (sobrepostos), porque não faz sentido armazenar as soluções se elas não forem necessárias novamente. Por exemplo, a pesquisa binária não tem subproblemas comuns. Se tomarmos um exemplo do seguinte programa recursivo para Números de Fibonacci, existem muitos subproblemas que são resolvidos repetidamente.

/* a simple recursive program for Fibonacci numbers */
int fib(int n)
{
    if (n <= 1)
        return n;
 
    return fib(n - 1) + fib(n - 2);
}

#  a simple recursive program for Fibonacci numbers
def fib(n):
    if n <= 1:
        return n
 
    return fib(n - 1) + fib(n - 2)

Árvore de recursão para execução de 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)

Podemos ver que a função fib (3) está sendo chamada 2 vezes. Se tivéssemos armazenado o valor de fib (3), em vez de computá-lo novamente, poderíamos ter reutilizado o antigo valor armazenado. Existem duas maneiras diferentes de armazenar os valores para que esses valores possam ser reutilizados:
a) Memorização (de cima para baixo)
b) Tabulação (de baixo para cima)

a) Memoização (Top Down): O programa memoizado para um problema é semelhante à versão recursiva com uma pequena modificação que examina uma tabela de pesquisa antes de calcular as soluções. Inicializamos um array de pesquisa com todos os valores iniciais como NIL. Sempre que precisamos da solução para um subproblema, primeiro examinamos a tabela de pesquisa. Se o valor pré-calculado estiver lá, retornamos esse valor; caso contrário, calculamos o valor e colocamos o resultado na tabela de pesquisa para que possa ser reutilizado posteriormente.

A seguir está a versão memorizada para o enésimo número de Fibonacci.

/* C++ program for Memoized version
for nth Fibonacci number */
#include <bits/stdc++.h>
using namespace std;
#define NIL -1
#define MAX 100
 
int lookup[MAX];
 
/* Function to initialize NIL
values in lookup table */
void _initialize()
{
    int i;
    for (i = 0; i < MAX; i++)
        lookup[i] = NIL;
}
 
/* function for nth Fibonacci number */
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];
}
 
// Driver code
int main ()
{
    int n = 40;
    _initialize();
    cout << "Fibonacci number is " << fib(n);
    return 0;
}
 
// This is code is contributed by rathbhupendra

/* C program for Memoized version for nth Fibonacci number */
#include<stdio.h>
#define NIL -1
#define MAX 100
 
int lookup[MAX];
 
/* Function to initialize NIL values in lookup table */
void _initialize()
{
  int i;
  for (i = 0; i < MAX; i++)
    lookup[i] = NIL;
}
 
/* function for nth Fibonacci number */
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 program for Memoized version */
public class Fibonacci
{
  final int MAX = 100;
  final int NIL = -1;
 
  int lookup[] = new int[MAX];
 
  /* Function to initialize NIL values in lookup table */
  void _initialize()
  {
    for (int i = 0; i < MAX; i++)
        lookup[i] = NIL;
  }
 
  /* function for nth Fibonacci number */
  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));
  }
 
}
// This Code is Contributed by Saket Kumar

# a program for Memoized version of nth Fibonacci number
 
# function to calculate nth Fibonacci number
def fib(n, lookup):
 
    # base case
    if n <= 1 :
        lookup[n] = n
 
    # if the value is not calculated previously then calculate it
    if lookup[n] is None:
        lookup[n] = fib(n-1 , lookup)  + fib(n-2 , lookup)
 
    # return the value corresponding to that value of n
    return lookup[n]
# end of function
 
# Driver program to test the above function
def main():
    n = 34
    # Declaration of lookup table
    # Handles till n = 100
    lookup = [None] * 101
    print "Fibonacci Number is ", fib(n, lookup)
 
if __name__=="__main__":
    main()
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

// C# program for Memoized versionof nth Fibonacci number
using System;
 
class GFG
{
     
    static int MAX = 100;
    static int NIL = -1;
    static int []lookup = new int[MAX];
     
    /* Function to initialize NIL
    values in lookup table */
    static void initialize()
    {
        for (int i = 0; i < MAX; i++)
            lookup[i] = NIL;
    }
     
    /* function for nth Fibonacci number */
    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];
    }
     
    // Driver code
    public static void Main()
    {
     
        int n = 40;
        initialize();
        Console.Write("Fibonacci number is" + " " + fib(n));
    }
}
 
// This Code is Contributed by Sam007

<script>
 
let  MAX = 100;
let NIL = -1;
 
let lookup = new Array(MAX);
 
function  _initialize()
{
    for (let i = 0; i < MAX; i++)
        lookup[i] = NIL;
}
 
function fib(n)
{
    if (lookup[n] == NIL)
    {
      if (n <= 1)
          lookup[n] = n;
      else
          lookup[n] = fib(n-1) + fib(n-2);
    }
    return lookup[n];
}
 
 
let n = 40;
_initialize();
document.write("Fibonacci number is" + " " + fib(n)+"<br>");
 
// This code is contributed by avanitrachhadiya2155
</script>

Saída

O número de Fibonacci é 102334155

b) Tabulação (Bottom Up): O programa tabulado para um determinado problema constrói uma tabela de baixo para cima e retorna a última entrada da tabela. Por exemplo, para o mesmo número de Fibonacci, primeiro calculamos fib (0), em seguida, fib (1), em seguida, fib (2) e, em seguida, fib (3) e assim por diante. Então, literalmente, estamos construindo as soluções dos subproblemas de baixo para cima.

A seguir está a versão tabulada para o enésimo número de Fibonacci.

/* C program for Tabulated version */
#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 program for Tabulated version */
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));
  }
 
}
// This Code is Contributed by Saket Kumar

# Python program Tabulated (bottom up) version
def fib(n):
 
    # array declaration
    f = [0] * (n + 1)
 
    # base case assignment
    f[1] = 1
 
    # calculating the fibonacci and storing the values
    for i in xrange(2 , n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]
 
# Driver program to test the above function
def main():
    n = 9
    print "Fibonacci number is " , fib(n)
 
if __name__=="__main__":
    main()
 
# This code is contributed by Nikhil Kumar Singh (nickzuck_007)

// C# program for Tabulated version
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));
    }
}
 
// This Code is Contributed by Sam007

<script>
 
// Javascript program for Tabulated version
function fib(n)
{
    var f = new Array(n + 1);
    var i;
     
    f[0] = 0;
    f[1] = 1;
    for(i = 2; i <= n; i++)
        f[i] = f[i - 1] + f[i - 2];
     
    return f[n];
}
 
// Driver code
var n = 9;
document.write("Fibonacci number is  " + fib(n));
 
// This code is contributed by akshitsaxenaa09
 
</script>

<?php
// PHP program for Tabulated version
 
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];
}
 
// Driver Code
$n = 9;
echo("Fibonacci number is ");
echo(fib($n));
 
// This code is contributed by nitin mittal.
?>

Saída

O número de Fibonacci é 34

Tanto o Tabulado quanto o Memoizado armazenam as soluções dos subproblemas. Na versão Memoizada, a tabela é preenchida sob demanda, enquanto na versão Tabulada, a partir da primeira entrada, todas as entradas são preenchidas uma a uma. Ao contrário da versão tabulada, todas as entradas da tabela de pesquisa não são necessariamente preenchidas na versão Memoizada. Por exemplo, a solução memorizada do problema LCS não preenche necessariamente todas as entradas.

Para ver a otimização alcançada por soluções memoized e tabulados sobre a solução recursiva básico, ver o tempo necessário seguindo pistas para calcular 40 número de Fibonacci:
recursiva solução
memoized solução
Tabulated solução
Tempo tomada pelo método de recursão é muito mais do que as duas técnicas de programação dinâmica mencionado acima - Memorização e Tabulação!

Além disso, consulte o método 2 da postagem de Número Feio para mais um exemplo simples em que temos subproblemas sobrepostos e armazenamos os resultados dos subproblemas.

Estaremos cobrindo a Propriedade de Subestrutura Ótima e mais alguns problemas de exemplo em postagens futuras sobre Programação Dinâmica.

Experimente as seguintes perguntas como um exercício desta postagem.
1) Escreva uma solução Memoized para o problema LCS. Observe que a solução tabular é fornecida no livro CLRS.
2) Como você escolheria entre Memorização e Tabulação?

Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima.
Referências:
http://www.youtube.com/watch?v=V5hZoJ6uK-s

Acervo Lima

O maior acervo de tutoriais e referências

Propriedade de subproblemas sobrepostos na programação dinâmica | DP-1

Latest posts

Latest posts

Most popular posts