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 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. usado O tipo de problemas que o DP pode resolver deve atender a dois critérios: . 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”. 1. Subestrutura ideal 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. . 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. 2. Subproblemas sobrepostos 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: é 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. 1. A memorização (abordagem de cima para baixo) esta abordagem usa memória de pilha por meio de chamadas de métodos recursivos Contras: Flexibilidade para tarefas de DP. Prós: é implementada usando um método iterativo. Os subproblemas do menor ao inicial são calculados sucessivamente, iterativamente. 2. A tabulação (abordagem bottom-up) 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. Contras: uso eficiente de memória, pois tudo é executado em uma única função. Prós: 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: Abordagem direta: quais são as desvantagens? Uma solução otimizada usando memoização 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 é chamada cinco vezes e 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. fib(1) fib(2) Análise Matemática: O (2n), Complexidade de tempo: 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. Complexidade do Espaço: Essa abordagem é extremamente ineficiente. Por exemplo, são necessárias 1.073.741.824 operações para calcular o 30º elemento. Resultado: 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 . Ele retorna o controle para o destacado. fib(2) fib(3) O destacado encontra seu valor após somar os resultados das chamadas e , insere sua solução no memorando e retorna o controle para . fib(3) fib(2) fib(1) fib(4) Chegamos ao estágio de reutilização da experiência anterior - quando o controle é retornado para , a chamada aguarda sua vez nele. por sua vez, em vez de chamar ( ), usa toda a solução finalizada do memorando e a retorna imediatamente. fib(4) fib(2) fib(2) fib(1) + fib(0) é calculado e retorna o controle para , que só precisa iniciar . Na última analogia, retorna imediatamente um valor do memorando sem cálculos. fib(4) fib(5) fib(3) fib(3) 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) 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. Resultado: 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: . Como conhecemos os elementos anteriores, podemos facilmente calcular o próximo, o seguinte e assim por diante. fib(n) = fib(n-1) + fib(n-2) 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) Esta abordagem é tão eficaz quanto a memoização em termos de velocidade, mas utiliza uma quantidade constante de memória. Resultado: Problema: Árvores Binárias Únicas Vejamos um 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. problema Uma é 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. árvore binária 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. Cada árvore começa no nó superior (vértice da árvore). A árvore então se expande em profundidade. 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 , precisamos considerar todas as variantes para distribuição de nossos nós. Eles são mostrados na tabela: numOfUniqueTrees(6) 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) , pois não temos nós à direita. O resultado é — o número de subárvores exclusivas à esquerda com uma direita constante. numOfUniqueTrees(5) * numOfUniqueTrees(0) numOfUniqueTrees(5) 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 por analogia anterior. numOfUniqueTrees(4) * numOfUniqueTrees(0) -> numOfUniqueTrees(4) Calculando . Se alocarmos um nó ao vértice, teremos 3 restantes. numOfUniqueTrees(4) 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 = 14. numOfUniqueTrees(4) 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, = 42. numOfUniqueTrees(5) Voltemos ao cálculo de , que é igual à soma das distribuições. numOfUniqueTrees(6) (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, seria chamado 18 vezes (tela abaixo). Com o aumento de N, as repetições do mesmo cálculo seriam muito maiores. numOfUniqueTrees(3) 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.

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Este áudio é produzido no idioma original da história!

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

Muito longo; Para ler

@indrivetech

Credibility

HISTÓRIAS RELACIONADAS