Programação dinâmica facilitada

Programação dinâmica facilitada

15 de September, 2020 0 By António César de Andrade
Click to rate this post!
[Total: 0 Average: 0]


A Programação Dinâmica é uma abordagem em que o problema principal é dividido em subproblemas menores, mas esses subproblemas não são resolvidos de forma independente.

Para que um problema seja resolvido usando programação dinâmica, os subproblemas devem ser sobrepostos. Isso significa que dois ou mais subproblemas serão avaliados para dar o mesmo resultado.

Assim, usamos a técnica de memoização para lembrar o resultado dos subproblemas já resolvidos para uso futuro. Em seguida, usamos o armazenamento em cache para armazenar esse resultado, que é usado quando um subproblema semelhante é encontrado no futuro.

Agora, vamos examinar esse tópico com mais profundidade.

O que é memoização?

Memoização é a técnica de memorizar os resultados de certos estados específicos, que podem ser acessados ​​para resolver subproblemas semelhantes. Em outras palavras, é uma forma específica de armazenamento em cache.

Isso garante que os resultados já calculados sejam armazenados geralmente como um hashmap. Isso diminui o tempo de execução significativamente e também leva a um código menos complicado.

Mas sabemos que qualquer benefício tem o custo de alguma coisa. Portanto, quando usamos a programação dinâmica, a complexidade do tempo diminui enquanto a complexidade do espaço aumenta.

Diferentes abordagens em DP

Na programação dinâmica, podemos usar uma abordagem de cima para baixo ou uma abordagem de baixo para cima.

A abordagem de cima para baixo envolve resolver o problema de maneira direta e verificar se já calculamos a solução para o subproblema.

Esta abordagem inclui chamadas recursivas (chamadas repetidas da mesma função). Ele cria uma pilha de chamadas, o que resulta em custos de memória. Também é vulnerável a erros de estouro de pilha.

A abordagem ascendente inclui primeiro olhar para os subproblemas menores e, em seguida, resolver os subproblemas maiores usando a solução para os problemas menores.

Essa abordagem evita os custos de memória resultantes da recursão.

Mas tanto a abordagem de cima para baixo quanto a de baixo para cima na programação dinâmica têm a mesma complexidade de tempo e espaço. Portanto, no final, usar qualquer uma dessas abordagens não faz muita diferença.

Apenas uma nota rápida: a programação dinâmica não é um algoritmo. Mas eu vi algumas pessoas confundirem isso com um algoritmo (incluindo eu no início).

É usado apenas quando temos um subproblema de sobreposição ou quando são necessárias chamadas de recursão extensa. É uma forma de melhorar o desempenho dos algoritmos lentos existentes.

Isso significa, também, que a complexidade de tempo e espaço da programação dinâmica varia de acordo com o problema.

Exemplo de programação dinâmica

Agora, vamos resolver um problema para entender melhor como a programação dinâmica realmente funciona.

Considere o problema de encontrar a subseqüência comum mais longa das duas seqüências fornecidas.

‘gtcab’ e ‘gxtxab’

Podemos resolver esse problema usando uma abordagem ingênua, gerando todas as subseqüências para ambos e, então, encontrar a mais longa subseqüência comum entre elas.

Mas a complexidade de tempo dessa solução cresce exponencialmente à medida que o comprimento da entrada continua aumentando.

Então, como sabemos que esse problema pode ser resolvido usando programação dinâmica?‌‌‌‌

Para as duas strings que tomamos, usamos o processo abaixo para calcular a subseqüência comum mais longa (LCS).

Como podemos ver, dividimos aqui o problema principal em subproblemas menores. Vamos verificar se algum subproblema está se repetindo aqui.

Dividindo o problema principal em subproblemas

‌‌ Podemos ver aqui que dois subproblemas se sobrepõem quando dividimos o problema em dois níveis.

Se continuarmos a dividir a árvore, poderemos ver muitos outros subproblemas que se sobrepõem. Portanto, concluímos que isso pode ser resolvido usando programação dinâmica.

A seguir, vamos examinar a abordagem geral por meio da qual podemos encontrar a mais longa subseqüência comum (LCS) usando a programação dinâmica.

Como preencher a matriz?

Usaremos o método de matriz para entender a lógica de resolver a subseqüência comum mais longa usando programação dinâmica.

Aqui, discutiremos apenas como resolver esse problema – ou seja, a parte do algoritmo. E para isso usamos o método da matriz.

Observe a matriz abaixo. Preenchemos a primeira linha com a primeira sequência e a primeira coluna com a segunda sequência.

Em seguida, populamos a segunda linha e a segunda coluna com zeros para o algoritmo iniciar. Denotamos as linhas com ‘Eu’ e colunas com ‘j’.

Entrada de matriz
Entrada de matriz

Agora avançamos para preencher as células da matriz. Compare as duas sequências até a célula específica onde estamos prestes a fazer a entrada.

O comprimento / contagem de subseqüências comuns permanece o mesmo até que o último caractere de ambas as seqüências submetidas à comparação se torne o mesmo.

Se as sequências que estamos comparando não tiverem seu último caractere igual, a entrada será o máximo da entrada na coluna à esquerda dela e a entrada da linha acima dela.

Quando os últimos caracteres de ambas as sequências são iguais, a entrada é preenchida aumentando a entrada diagonal superior esquerda dessa célula em particular 1.

A lógica que usamos aqui para preencher a matriz é fornecida abaixo: ‌

if(input[i]==input[j])              //Check if last characters are equal
T[i][j]=T[i-1][j-1]+1               //Entry is incremental of upper left element
else                                //If the last character are not equal
T[i][j]=max(T[i-1][j], T[i][j-1])   //Entry is max of element to its left and top

A entrada inferior direita de toda a matriz nos dá o comprimento da subseqüência comum mais longa.

Encontrando a subseqüência comum mais longa

Para obter a subseqüência comum mais longa, temos que atravessar a partir do canto inferior direito da matriz. Em seguida, verificamos de onde vem a entrada específica.

Ou seja, podemos verificar se é o máximo de sua entrada esquerda e superior ou então é o entrada incremental do elemento diagonal superior esquerdo?

Repetimos esse processo até chegar ao canto superior esquerdo da matriz. A sub-sequência que obtemos ao combinar o caminho que percorremos (considere apenas aqueles caracteres onde a seta se move diagonalmente) estará na ordem inversa.

Temos que reverter essa sequência obtida para obter a subseqüência comum mais longa correta. Portanto, neste exemplo específico, a subseqüência comum mais longa é ‘gtab’.

Fiz um vídeo detalhado sobre como preenchemos a matriz para que você possa entender melhor. Você pode encontrá-lo aqui: Explicação em vídeo.

O que aprendemos?

Neste artigo, aprendemos o que é programação dinâmica e como identificar se um problema pode ser resolvido usando a programação dinâmica.

Em seguida, passamos a estudar a complexidade de um problema de programação dinâmica.

Em seguida, aprendemos como podemos resolver o problema comum de subseqüência mais longo usando a programação dinâmica.

Espero que tenham gostado e aprendido algo útil com este artigo.

Se você achou esta postagem útil, por favor, compartilhe. Se você tiver algum feedback, sinta-se à vontade para entrar em contato comigo no Twitter.





Fonte