Compreendendo a programação dinâmica para que você possa usá-la de maneira eficaz

Este artigo não está relacionado ao desenvolvimento de produção, mas diz respeito à programação. Discutirei a Programação Dinâmica (DP) e como usar a experiência anterior em computação de maneira eficaz. Espero que você ache interessante.

Introdução à Programação Dinâmica

O termo Programação Dinâmica foi usado pela primeira vez pelo famoso matemático americano, um dos maiores especialistas em tecnologia da computação, Richard Bellman, na década de 1950. A Programação Dinâmica (DP) é um método de resolver tarefas complexas, dividindo-as em subproblemas menores.

O tipo de problemas que o DP pode resolver deve atender a dois critérios:

1. Subestrutura ideal . A programação dinâmica significa que a solução para subproblemas menores pode ser usada para resolver o problema inicial. A subestrutura ótima é a principal característica do paradigma “Dividir para Conquistar”.

Um exemplo clássico de implementação é o algoritmo merge sort, no qual recursivamente dividimos o problema nos subproblemas mais simples (matrizes de tamanho 1), após os quais fazemos cálculos com base em cada um deles. Os resultados são usados para resolver a próxima camada (subproblemas maiores) até que a camada inicial seja alcançada.

2. Subproblemas sobrepostos . Na ciência da computação, diz-se que um problema tem subproblemas sobrepostos se o problema puder ser dividido em subproblemas que são reutilizados várias vezes. Em outras palavras, executar o mesmo código com os mesmos dados de entrada e os mesmos resultados. Um exemplo clássico desse problema é o cálculo de um N-ésimo elemento em uma sequência de Fibonacci, que veremos a seguir.

Poderíamos dizer que DP é um caso especial do uso do paradigma Dividir e Conquistar, ou uma versão mais complexa dele. O padrão é adequado para resolver tarefas que envolvem combinatória, onde um grande número de combinações diferentes é calculado, mas a quantidade N de elementos é frequentemente monótona e idêntica.

Nos problemas de subestrutura ótima e subproblemas sobrepostos, temos numerosos cálculos e operações repetidas, se aplicarmos uma abordagem de força bruta. DP nos ajuda a otimizar a solução e evitar a duplicação da computação usando duas abordagens principais: memoização e tabulação:

1. A memorização (abordagem de cima para baixo) é implementada por meio de recursão. Uma tarefa é dividida em subproblemas menores, seus resultados são armazenados na memória e combinados para resolver o problema original por meio do uso repetido.

• Contras: esta abordagem usa memória de pilha por meio de chamadas de métodos recursivos
• Prós: Flexibilidade para tarefas de DP.

2. A tabulação (abordagem bottom-up) é implementada usando um método iterativo. Os subproblemas do menor ao inicial são calculados sucessivamente, iterativamente.

• Contras: gama limitada de aplicação. Esta abordagem requer uma compreensão inicial de toda a sequência de subproblemas. Mas em alguns problemas isso não é viável.
• Prós: uso eficiente de memória, pois tudo é executado em uma única função.

A teoria pode parecer tediosa e incompreensível — vejamos alguns exemplos.

Problema: Sequência de Fibonacci

Um exemplo clássico de DP é calcular um N-ésimo elemento em uma sequência de Fibonacci, onde cada elemento é a soma dos dois anteriores, e o primeiro e o segundo elementos são iguais a 0 e 1.

Por hipótese, focamos inicialmente na natureza da subestrutura ótima, pois, para calcular um valor, precisamos encontrar o anterior. Para calcular o valor anterior, precisamos de determinar aquele que veio antes dele e assim por diante. A natureza das subtarefas sobrepostas é ilustrada no diagrama abaixo.

Para esta tarefa, examinaremos três casos:

1. Abordagem direta: quais são as desvantagens?
2. Uma solução otimizada usando memoização
3. Uma solução otimizada usando tabulação

Abordagem direta/de força bruta

A primeira coisa que você pode pensar é inserir a recursão, somar os dois elementos anteriores e fornecer o resultado.

 /** * Straightforward(Brute force) approach */ fun fibBruteForce(n: Int): Int { return when (n) { 1 -> 0 2 -> 1 else -> fibBruteForce(n - 1) + fibBruteForce(n - 2) } }

Na tela abaixo, você pode ver uma pilha de chamadas de função, para calcular o quinto elemento da sequência.

Observe que a função fib(1) é chamada cinco vezes e fib(2) três vezes. Funções com uma assinatura, com os mesmos parâmetros, são iniciadas repetidamente e fazem a mesma coisa. Quando o número N aumenta, a árvore aumenta, não linearmente, mas exponencialmente, o que leva a uma duplicação colossal de cálculos.

Análise Matemática:

Complexidade de tempo: O (2n),

Complexidade do Espaço: O(n) -> proporcional à profundidade máxima da árvore recursiva, pois este é o número máximo de elementos que podem estar presentes na pilha de chamadas de função implícitas.

Resultado: Essa abordagem é extremamente ineficiente. Por exemplo, são necessárias 1.073.741.824 operações para calcular o 30º elemento.

Memoização (abordagem de cima para baixo)

Nesta abordagem, a implementação não é muito diferente da solução de “força bruta” anterior, exceto a alocação de memória. Que seja a variável memo, na qual coletamos os resultados dos cálculos de qualquer função fib() concluída em nossa pilha.

Deve-se notar que teria sido suficiente ter um array de inteiros e referir-se a ele por índice, mas, por uma questão de clareza conceitual, foi criado um mapa hash.

 /** * Memoization(Top-down) approach */ val memo = HashMap<Int, Int>().apply { this[1] = 0 this[2] = 1 } fun fibMemo(n: Int): Int { if (!memo.containsKey(n)) { val result = fibMemo(n - 1) + fibMemo(n - 2) memo[n] = result } return memo[n]!! }

Vamos nos concentrar novamente na pilha de chamadas de função:

• A primeira função concluída que grava o resultado no memorando é a destacada fib(2) . Ele retorna o controle para o fib(3) destacado.
• O fib(3) destacado encontra seu valor após somar os resultados das chamadas fib(2) e fib(1) , insere sua solução no memorando e retorna o controle para fib(4) .
• Chegamos ao estágio de reutilização da experiência anterior - quando o controle é retornado para fib(4) , a chamada fib(2) aguarda sua vez nele. fib(2) por sua vez, em vez de chamar ( fib(1) + fib(0) ), usa toda a solução finalizada do memorando e a retorna imediatamente.
• fib(4) é calculado e retorna o controle para fib(5) , que só precisa iniciar fib(3) . Na última analogia, fib(3) retorna imediatamente um valor do memorando sem cálculos.

Podemos observar uma redução no número de chamadas de funções e cálculos. Além disso, quando N aumenta, haverá exponencialmente menos reduções.

Análise Matemática:

Complexidade de tempo: O(n)

Complexidade Espacial: O(n)

Resultado: há uma diferença clara na complexidade assintótica. Esta abordagem reduziu-o a linear no tempo, em comparação com a solução primitiva, e não o aumentou na memória.

Tabulação (abordagem de baixo para cima)

Conforme mencionado acima, esta abordagem envolve cálculo iterativo de um subproblema menor para um subproblema maior. No caso de Fibonacci, os menores “subproblemas” são o primeiro e o segundo elementos da sequência, 0 e 1, respectivamente.

Sabemos bem como os elementos se relacionam entre si, o que é expresso na fórmula: fib(n) = fib(n-1) + fib(n-2) . Como conhecemos os elementos anteriores, podemos facilmente calcular o próximo, o seguinte e assim por diante.

Ao somar os valores que conhecemos, podemos encontrar o próximo elemento. Implementamos esta operação ciclicamente até encontrarmos o valor desejado.

 /** * Tabulation(Bottom-up) approach fun fibTab(n: Int): Int { var element = 0 var nextElement = 1 for (i in 2 until n) { val newNext = element + nextElement element = nextElement nextElement = newNext } return nextElement }

Análise Matemática:

Complexidade de tempo: O(n)

Complexidade Espacial: O(1)

Resultado: Esta abordagem é tão eficaz quanto a memoização em termos de velocidade, mas utiliza uma quantidade constante de memória.

Problema: Árvores Binárias Únicas

Vejamos um problema mais complexo: precisamos encontrar o número de todas as árvores binárias estruturalmente únicas que podem ser criadas a partir de N nós.

Uma árvore binária é uma estrutura de dados hierárquica, na qual cada nó possui no máximo dois descendentes. Como regra geral, o primeiro é chamado de nó pai e tem dois filhos – o filho esquerdo e o filho direito.

Vamos supor que precisamos encontrar uma solução para N = 3. Existem 5 árvores estruturalmente únicas para os três nós. Podemos contá-los em nossa cabeça, mas se o N for aumentado, as variações aumentariam imensamente e seria impossível visualizá-las em nossa cabeça.

Esta tarefa poderia ser atribuída à combinatória. Vamos descobrir quais combinações podem ser formadas e como podemos encontrar um padrão para sua formação.

1. Cada árvore começa no nó superior (vértice da árvore). A árvore então se expande em profundidade.
2. Cada nó é o início de uma nova árvore filha (subárvore), conforme mostrado na tela. A subárvore esquerda é verde e a direita é vermelha. Cada um tem seu próprio vértice.

Vejamos um exemplo de tarefa, onde N = 6 no nível conceitual. Chamaremos nossa função de cálculo numOfUniqueTrees(n: Int) .

No nosso exemplo, são dados 6 nós, um dos quais, de acordo com o princípio mencionado anteriormente, forma o vértice da árvore, e os outros 5 — o restante.

A partir de agora, interagimos com os restantes nós. Isso pode ser feito de várias maneiras. Por exemplo, usando todos os cinco nós para formar a subárvore esquerda ou enviando todos os cinco para a subárvore direita. Ou dividindo os nós em dois – 2 à esquerda e 3 à direita (veja a tela abaixo), temos um número limitado dessas variantes.

Para alcançar o resultado numOfUniqueTrees(6) , precisamos considerar todas as variantes para distribuição de nossos nós. Eles são mostrados na tabela:

A tabela mostra 6 distribuições diferentes dos nós. Se descobrirmos quantas árvores únicas podem ser geradas para cada distribuição e somarmos, alcançaremos nosso resultado final.

Como encontrar o número de árvores únicas para distribuição?

Temos dois parâmetros: Nós esquerdos e Nós direitos (coluna esquerda e direita da tabela).

O resultado será igual a: numOfUniqueTrees(leftNodes) * numOfUniqueTrees(rightNodes) .

Por que? À esquerda teremos X árvores únicas e, para cada uma, poderemos colocar Y variações únicas de árvores à direita. Multiplicamos isso para obter o resultado.

Então, vamos descobrir as variações para a primeira distribuição (5 à esquerda, 0 à direita)

numOfUniqueTrees(5) * numOfUniqueTrees(0) , pois não temos nós à direita. O resultado é numOfUniqueTrees(5) — o número de subárvores exclusivas à esquerda com uma direita constante.

Calculando numOfUniqueTrees(5) .

Agora temos o menor subproblema. Estaremos operando com ele como fizemos com o maior. Nesta fase, a característica das tarefas DP é clara – subestrutura ótima, comportamento recursivo.

Um nó (o nó verde) é enviado ao vértice. Distribuímos os (quatro) nós restantes de forma análoga à experiência anterior (4:0), (3:1), (2:2), (1:3), (0:4).

Calculamos a primeira distribuição (4:0). É igual a numOfUniqueTrees(4) * numOfUniqueTrees(0) -> numOfUniqueTrees(4) por analogia anterior.

Calculando numOfUniqueTrees(4) . Se alocarmos um nó ao vértice, teremos 3 restantes.

Distribuições (3:0), (2:1), (1:2), (0:3).

Para 2 nós existem apenas duas árvores binárias exclusivas, para 1 — uma. Anteriormente já mencionamos que existem 5 variações de árvores binárias únicas para três nós.

Como resultado — distribuições(3:0), (0:3) são iguais a 5, (2:1), (1:2) — 2. Se somarmos 5 + 2 + 2 + 5, obtemos 14 .numOfUniqueTrees numOfUniqueTrees(4) = 14.

Vamos inserir o resultado do cálculo na variável memo de acordo com a experiência de memoização. Sempre que precisarmos encontrar variações para quatro nós, não as calcularemos novamente, mas reutilizaremos a experiência anterior.

Voltemos ao cálculo (5:0), que é igual à soma das distribuições (4:0), (3:1), (2:2), (1:3), (0:4). Sabemos que (4:0) = 14. Vamos voltar ao memorando, (3:1) = 5, (2:2) = 4 (2 variações à esquerda * 2 à direita), (1:3) = 5, (0:4) = 14. Se somarmos isso, obtemos 42, numOfUniqueTrees(5) = 42.

Voltemos ao cálculo de numOfUniqueTrees(6) , que é igual à soma das distribuições.

(5:0) = 42, (4:1) = 14, (3:2) =10 (5 à esquerda * 2 à direita), (2:3) = 10, (1:4) = 14, (0: 5) = 42. Se somarmos isso, obtemos 132, numOfUniqueTrees(5) = 132 .

Tarefa resolvida!

Resultado: observemos os subproblemas sobrepostos na solução onde N = 6. Na solução direta, numOfUniqueTrees(3) seria chamado 18 vezes (tela abaixo). Com o aumento de N, as repetições do mesmo cálculo seriam muito maiores.

Destaco que o número de árvores únicas para (5 à esquerda, 0 à direita) e (0 à esquerda, 5 à direita) será o mesmo. Apenas em um caso eles estarão à esquerda e no outro à direita. Isso também funciona para (4 à esquerda, 1 à direita) e (1 à esquerda, 4 à direita).

A memorização, como abordagem de programação dinâmica, permitiu otimizar a solução para uma tarefa tão complexa.

Implementação

 class Solution { fun calculateTees(n: Int, memo:Array<Int?>): Int { var treesNum = 0 if(n < 1) return 0 if(n == 2) return 2 if(n == 1) return 1 if(memo[n]!=null) return memo[n]!! for (i in 1..n){ val leftSubTrees = calculateTees( i - 1, memo) val rightSubTrees = calculateTees(n - i, memo) treesNum += if(leftSubTrees>0 && rightSubTrees>0){ leftSubTrees*rightSubTrees } else leftSubTrees+leftSubTrees } memo[n] = treesNum return treesNum } } 

Conclusão

Em alguns casos, resolver tarefas por meio de Programação Dinâmica pode economizar muito tempo e fazer o algoritmo funcionar com máxima eficiência.

Obrigado por ler este artigo até o fim. Ficarei feliz em responder suas perguntas.