Introdução à programação dinâmica: sobreposição de subproblemas e subestrutura ótima

Publicados: 2021-02-08

Índice

Introdução

Vamos supor que temos uma questão para resolver o quadrado de 25. Se estivermos enfrentando essa questão pela primeira vez, podemos resolvê-la manualmente ou usando uma calculadora. Mas se já vimos essa pergunta antes ou resolvemos isso antes, existe a possibilidade de respondê-la rapidamente memorizando-a.

Isso nos leva à conclusão de que, se pudermos lembrá-lo, podemos ignorá-lo na próxima vez. A programação dinâmica funciona em um conceito semelhante, a ideia é lembrar o resultado de uma computação e usá-lo no futuro, se necessário.

Esse procedimento simples de programação dinâmica torna uma arma forte para um programador vencer a batalha do código eficiente.

Por exemplo, vamos supor que temos uma questão complexa e sempre pensamos em uma solução que divide a questão em subproblemas. Mas podemos ficar presos em uma situação em que vamos calcular um subproblema várias vezes. Lá usamos programação dinâmica para uma solução ótima.

A programação dinâmica tem dois conceitos:

  1. Subproblemas sobrepostos
  2. Subestrutura ideal

Subproblemas sobrepostos

Um exemplo clássico de compreensão do conceito de subproblema sobreposto é um programa para imprimir a série de Fibonacci.

A lógica da série de Fibonacci é dada por “fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)”. E executar essa função perfeitamente pode ser feito usando uma solução recursiva, com um caso base de fibonacci(0)=0 e fibonacci(1)=1.

public static int fibonacci(int n){
 se (n== 0 || n== 1 )
 retornar n;
 return fibonacci(n -1 )+fibonacci(n -2 );
 }
 public static void main(String[] args){
 System.out.print( “4º número de fibonacci é “ +fibonacci( 4 ));
 }

Digamos que precisamos imprimir o 4º dígito de fibonacci, então a árvore de recursão fica como

fibonacci(4)

/\

fibonacci(3) + fibonacci(2)

/ \ / \

fibonacci(2) + fibonacci(1) fibonacci(1) + fibonacci(0)

/\

fibonacci(1) + fibonacci(0)

Observe que fibonacci(4) é o 5º dígito na série de fibonacci porque começamos de fibonacci(0). Na árvore de recursão acima, podemos ver que fibonacci(2) é repetido duas vezes. Observamos duplicação em uma árvore de recursão de altura 4, agora imagine que temos uma chamada recursiva de um número enorme e, posteriormente, haverá uma árvore de recursão com uma grande altura. E haverá muitos desses cálculos duplicados, conhecidos como subproblemas sobrepostos.

Temos dois métodos para lidar com essa (i) tabulação, (ii) memorização

Vamos entendê-los percorrendo suas implementações.

Memorização

Resolver o problema de fibonacci usando o método de memoização pode ser feito como mostrado abaixo

memorando int[] estático;
public static int fibonacci(int n){
if(memorando[n]!=-1)
return memorando[n];
if(n==0 || n==1){
memorando[n]=n;
retornar n;
}
memo[n] = fibonacci(n-1)+fibonacci(n-2);
return memorando[n];
}
public static void main(String[] args){
memorando=novo int[5];
for(int i=0;i<=4;i++)
memorando[i]=-1;
System.out.println(“4º número de fibonacci é “+fibonacci(4));
}

No código acima, estamos criando um arquivo de log de manutenção ou mantendo uma tabela de pesquisa e armazenando os valores dos resultados calculados. Como memorizamos todos os valores calculados, podemos usá-los no futuro, se necessário, evitando cálculos duplicados e subproblemas sobrepostos.

Toda a lógica é semelhante à solução recursiva, mas a única diferença que fizemos é que estamos anotando-os no array memo antes de retornarmos o valor ao método main. A única restrição para este algoritmo é que precisamos de um espaço extra de tamanho O(n), mas estamos otimizando a solução recursiva anterior.

Tabulação

Este método é um pouco diferente da solução acima. A memoização segue a mesma solução recursiva. Mas na tabulação, seguimos uma solução iterativa. Também é chamada de abordagem de baixo para cima. Vejamos a implementação da abordagem de baixo para cima.

public static int fibonacci(int n){
 int tabela[]=novo int[n+ 1 ];
 for (int i= 0 ;i<=n;i++){
 if (i== 0 || i== 1 )
 tabela[i]=i;
 senão {
 tabela[i]=tabela[i -1 ]+tabela[i -2 ];
 }
 }
 retornar tabela[n];
 }
 public static void main(String[] args){
 System.out.println( “4º número de fibonacci é “ +fibonacci( 4 ));
 }

Como sabemos que fibonacci(n)=fibonacci(n-1)+fibonacci(n-2), na memoização começamos com a chamada de função fibonacci(4), e então percebemos que não calculamos seu valor, então nós 've calculado seus valores e, em seguida, armazenou.

Uma situação semelhante será enfrentada por outras chamadas recursivas como fibonacci(3), fibonacci(2). Agora, isso faz com que muitas chamadas recursivas esperem na pilha de recursão, mas de qualquer maneira estamos pulando a duplicação dos subproblemas sobrepostos.

Também temos uma maneira de calcular fibonacci de 0 a n-ésimo elemento iterativamente e, em seguida, retornar o n-ésimo elemento de fibonacci. Isso é o que implementamos no código acima. Este código também tem o mesmo requisito de espaço O(n).

Checkout: Habilidades para se tornar um desenvolvedor full stack

Subestrutura Ótima

Neste conceito, podemos obter uma solução ótima para um problema somente se tivermos resolvido de forma ótima seus subproblemas correspondentes.

E um exemplo clássico desse conceito é considerar uma travessia entre nós em um grafo.

Vamos supor que temos múltiplas raízes de Telangana a Delhi. E se tivermos a rota mais curta que passa por Nagpur e Gwalior. Então a rota mais curta de Nagpur a Delhi Delhi deve passar por Gwalior. Agora podemos dividir nosso problema em subproblemas que são Telangana para Nagpur, Nagpur para Gwalior, Gwalior para Delhi.

E um exemplo clássico para essa propriedade é a subsequência comum mais longa em ambas as strings. Uma subsequência é diferente de uma substring. Em uma subsequência, os caracteres não precisam ser conseqüentes na string original.

Portanto, a ideia é resolvê-lo resolvendo seus subproblemas de forma otimizada. Seja n o comprimento da subsequência comum mais longa.

Se n=LCS(batata, tattoo), então n=LCS(potat,tatto)+1 (se os últimos caracteres forem iguais), senão n=maximum(LCS(potato,tatto), LCS(potat, tattoo).

static int lcs(String s1, String s2, int m, int n ){
 int dp[][] = new int[m+ 1 ][n+ 1 ];
 for (int i= 0 ; i<=m; i++){
 for (int j= 0 ; j<=n; j++){
 if (i == 0 || j == 0 )
 dp[i][j] = 0 ;
 senão if (s1.charAt(i -1 ) == s2.charAt(j -1 ))
 dp[i][j] = dp[i - 1 ][j - 1 ] +1 ;
 outro
 dp[i][j] = Math.max(dp[i -1 ][j], dp[i][j -1 ]);
 }
 }
 return dp[m][n];
 }
 public static void main(String[] args){
 System.out.println( “a extensão da subsequência comum mais longa é “ +lcs( “batata” , “tatuagem” , 6 , 6 ));
 }

No código acima, implementamos nossa lógica usando o método de tabulação e computamos o comprimento da subsequência comum mais longa presente em ambas as strings.

Leia também: Salário Full Stack Developer na Índia

Aprenda cursos de desenvolvimento de software online das melhores universidades do mundo. Ganhe Programas PG Executivos, Programas de Certificado Avançado ou Programas de Mestrado para acelerar sua carreira.

Conclusão

Agora que você está ciente de como usar uma das técnicas poderosas para vencer a batalha do código eficiente, tente implementar a programação dinâmica para outros problemas e comece a fortalecer sua capacidade de codificar uma questão usando programação dinâmica.

Para concluir, os cursos Full Stack Developers são especialistas altamente qualificados que podem lidar com tudo relacionado ao desenvolvimento web. Essas habilidades de Desenvolvedor Full Stack são o que os distingue dos Desenvolvedores Frontend e Backend.

O que é programação dinâmica?

Um programa de computador contém muito código repetitivo. Isso é ineficiente e pode afetar seu desempenho. Neste caso, a programação dinâmica é usada. A programação dinâmica é um método de resolver um problema complexo dividindo-o em subproblemas mais simples, resolvendo cada um desses subproblemas apenas uma vez e armazenando suas soluções usando tabelas, que são consultadas sempre que um subproblema semelhante ocorre mais tarde em a solução do problema complexo. Algoritmos de programação dinâmica são usados ​​para resolver vários tipos de problemas de otimização nas áreas de pesquisa operacional, estimativa estatística, reconhecimento de padrões, inteligência artificial, aprendizado de máquina, biologia computacional e outros campos.

O que é subproblema de sobreposição na programação dinâmica?

O subproblema sobreposto é um conceito usado quando os subproblemas têm soluções que também são usadas em outros subproblemas. Essa sobreposição faz com que a mesma subtarefa seja resolvida mais de uma vez. O problema é encontrar uma maneira de resolver a subtarefa apenas uma vez e usar essa solução para obter as soluções de outros subproblemas. Algoritmos de programação dinâmica resolvem esse problema usando memoização. A memoização é uma técnica onde armazenamos soluções para subproblemas para que não tenhamos que resolvê-los novamente.

O que é subestrutura ótima em programação dinâmica?

A subestrutura ótima implica que a solução ótima para um problema está relacionada a uma solução ótima para um problema menor dentro da mesma definição de problema. A subestrutura ótima é um requisito adicional necessário para resolver problemas ou provar que não há solução. Com subestrutura ótima, podemos provar muitos problemas NP-difíceis. Uma abordagem geral para resolver problemas de DP é usar uma matriz de programação dinâmica para armazenar a solução ótima de subproblemas. A matriz de programação dinâmica pode ser usada para resolver qualquer problema de DP de subestrutura ótima diferente de zero.