Programação dinâmica: características, exemplo, vantagens, desvantagens

Programação dinâmica: características, exemplo, vantagens, desvantagens

A programação dinâmica é um algoritmo de modelo que resolve um problema complexo dividindo -o em subproblemas, armazenando os resultados para evitar a necessidade de recalcular os resultados.

Essa programação é usada quando você tem problemas que podem ser divididos em subproblemas semelhantes, para que seus resultados possam ser reutilizados. A grande maioria desta programação é usada para otimização.

Antes de resolver o subproblema disponível, o algoritmo dinâmico tentará examinar os resultados dos subproblemas resolvidos anteriormente. As soluções de subproblemas são combinadas para obter a melhor solução.

Em vez de calcular o mesmo subproblema repetidamente, sua solução pode ser armazenada em alguma memória quando você encontra esse subproblema pela primeira vez. Quando ele aparecer novamente durante a solução de outro subproblema, a solução já armazenada na memória será usada.

É uma idéia maravilhosa para preencher o tempo de memória, onde o uso de espaço adicional pode melhorar o tempo necessário para encontrar uma solução.

Recursos de programação dinâmica

As seguintes características essenciais são as que devem ter um problema para que a programação dinâmica seja aplicada:

Subestrutura ideal

Essa característica expressa que um problema de otimização pode ser resolvido combinando as soluções ideais dos problemas secundários que o compõem. Essas subestruturas ótimas são descritas por recursão.

Por exemplo, em um gráfico, uma subestrutura ideal será apresentada no caminho mais curto r que vai de um vértice s a um vértice t:

Ou seja, nesse caminho mais curto r, qualquer vértice intermediário i pode ser usado. Se r é realmente a rota mais curta, pode ser dividida nas sub-rotinas r1 (de s a i) e r2 (de i a t), de modo que essas são as rotas mais curtas entre os vértices correspondentes.

Portanto, para encontrar as rotas mais curtas, a solução pode ser facilmente formulada recursivamente, que é o que o algoritmo de Floyd-Warshall faz.

Subproblemas sobrepostos

O espaço dos subproblemas deve ser pequeno. Em outras palavras, qualquer algoritmo recursivo que resolva um problema deve resolver os mesmos subproblemas repetidamente, em vez de gerar novos subproblemas.

Por exemplo, para gerar a série Fibonacci, podemos considerar esta formulação recursiva: Fn = F (n – 1) + F (n – 2), tomando como base o caso que F1 = F2 = 1. Então teremos que: F33 = F32 + F31 e F32 = F31 + F30.

Como você pode ver, o F31 está sendo resolvido nas subárvores recursivas do F33 e do F32. Embora o número total de subproblemas seja realmente pequeno, a adoção de uma solução recursiva como essa acabará resolvendo os mesmos problemas repetidamente.

Relacionado:  Topologia de barramento: recursos, vantagens, desvantagens

Isso é levado em consideração pela programação dinâmica, e resolve cada subproblema apenas uma vez. Isso pode ser realizado de duas maneiras:

Abordagem de cima para baixo

Se a solução para qualquer problema puder ser formulada recursivamente usando a solução de seus subproblemas, e se esses subproblemas se sobrepuserem, as soluções para os subproblemas poderão ser facilmente memorizadas ou armazenadas em uma tabela.

Sempre que um novo subproblema for procurado por uma solução, ele será verificado na tabela se tiver sido resolvido anteriormente. Se uma solução for armazenada, ela será usada em vez de calculá-la novamente. Caso contrário, o subproblema será resolvido, armazenando a solução na tabela.

Foco ascendente

Depois que a solução de um problema for recursivamente formulada em termos de seus subproblemas, você poderá tentar reformular o problema de uma maneira ascendente: primeiro você tentará resolver os subproblemas e usar suas soluções para chegar a soluções para os subproblemas maiores.

Isso geralmente também é feito em forma de tabela, gerando iterativamente soluções para subproblemas cada vez maiores, usando soluções para subproblemas menores. Por exemplo, se os valores de F31 e F30 já são conhecidos, o valor de F32 pode ser calculado diretamente.

Comparação com outras técnicas

Uma parte significativa de um problema que pode ser resolvido pela programação dinâmica é que ele deve ter subproblemas sobrepostos. É isso que distingue a programação dinâmica da técnica de dividir e conquistar, onde não é necessário armazenar os valores mais simples.

É semelhante à recursão, pois ao calcular casos base, o valor final pode ser determinado indutivamente. Essa abordagem de baixo para cima funciona bem quando um novo valor depende apenas dos valores calculados anteriormente.

Exemplo

Etapas mínimas para atingir 1

Para qualquer número inteiro positivo “e”, qualquer uma das três etapas a seguir pode ser executada.

– Subtraia 1 do número. (e = e-1).

– Se é divisível por 2, é dividido por 2 (se e% 2 == 0, então e = e / 2).

– Se é divisível por 3, é dividido por 3 (se e% 3 == 0, então e = e / 3).

Com base nas etapas acima, você deve encontrar o número mínimo dessas etapas para executar a EA 1. Por exemplo:

– Se e = 1, resultado: 0.

– Se e = 4, resultado: 2 (4/2 = 2/2 = 1).

– Quando e = 7, resultado: 3 (7-1 = 6/3 = 2/2 = 1).

Foco

Você pode sempre pensar em escolher a etapa que torna n o mais baixo possível e continuar assim, até chegar a 1. No entanto, você pode ver que essa estratégia não funciona aqui.

Relacionado:  Filtros ativos: características, primeira e segunda ordem

Por exemplo, se e = 10, as etapas seriam: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 etapas). No entanto, a maneira ideal é: 10-1 = 9/3 = 3/3 = 1 (3 etapas). Portanto, todas as etapas possíveis que podem ser executadas para cada valor de n devem ser testadas, escolhendo o número mínimo dessas possibilidades.

Tudo começa com a recursão: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} se e> 1, tomando como base: F (1) = 0. Com a equação de recorrência, você pode começar a codificar a recursão.

No entanto, pode-se ver que há subproblemas sobrepostos. Além disso, a solução ideal para uma determinada entrada depende da solução ótima de seus subproblemas.

Como na memorização, onde as soluções dos subproblemas resolvidos são armazenadas para uso posterior. Ou, como na programação dinâmica, você começa do fundo, progredindo para o e especificado. Então os dois códigos:

Memorização

Programação dinâmica de baixo para cima

Vantagem

Uma das principais vantagens do uso de programação dinâmica é que ela acelera o processamento, pois são usadas referências que foram calculadas anteriormente. Por ser uma técnica de programação recursiva, reduz as linhas do código do programa.

Algoritmos vorazes vs programação dinâmica

Os algoritmos vorazes são semelhantes à programação dinâmica, pois são as duas ferramentas para otimização. No entanto, o algoritmo voraz procura uma solução ideal em cada etapa local. Ou seja, ele procura uma escolha gananciosa na esperança de encontrar um ótimo global.

Assim, algoritmos vorazes podem fazer uma suposição que parece ótima no momento, mas que se torna cara no futuro e não garante uma ótima global.

Por outro lado, a programação dinâmica encontra a solução ideal para os subproblemas e, em seguida, faz uma escolha informada combinando os resultados desses subproblemas para realmente encontrar a solução mais ideal.

Desvantagens

– É necessária muita memória para armazenar o resultado calculado de cada subproblema, sem poder garantir que o valor armazenado será usado ou não.

– Muitas vezes, o valor de saída é armazenado sem nunca ser usado nos seguintes subproblemas durante a execução. Isso leva a um uso desnecessário de memória.

– Na programação dinâmica, as funções são chamadas recursivamente. Isso mantém a memória da pilha aumentando constantemente.

Recursão vs programação dinâmica

Se você tiver memória limitada para executar o código e a velocidade de processamento não for preocupante, a recursão poderá ser usada. Por exemplo, se você estiver desenvolvendo um aplicativo móvel, a memória é muito limitada para executar o aplicativo.

Relacionado:  50 blogs recomendados de videogame

Se você deseja que o programa funcione mais rápido e não tenha restrições de memória, é preferível usar a programação dinâmica.

Formulários

A programação dinâmica é um método eficaz de resolver problemas que, de outra forma, poderiam parecer extremamente difíceis de resolver em um período de tempo razoável.

Algoritmos baseados no paradigma de programação dinâmica são usados ​​em muitas áreas da ciência, incluindo muitos exemplos em inteligência artificial, desde a solução de problemas de planejamento até o reconhecimento de voz.

Algoritmos baseados em programação dinâmica

A programação dinâmica é bastante eficaz e funciona bem para uma ampla gama de problemas. Muitos algoritmos podem ser vistos como aplicativos de algoritmo vorazes, como:

– Série numérica de Fibonacci.

– Torres de Hanói.

– Todos os pares de rotas mais curtas através de Floyd-Warshall.

– Problema com mochila.

– Programação de projetos.

– O caminho mais curto através de Dijkstra.

– Controle de vôo e controle de robótica.

– Problemas de otimização matemática.

– Timeshare: programe o trabalho para maximizar o uso da CPU.

Série de números de Fibonacci

Os números de Fibonacci são os números que estão na seguinte sequência: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, etc.

Na terminologia matemática, a sequência Fn dos números de Fibonacci é definida pela fórmula de recorrência: F (n) = F (n -1) + F (n -2), onde F (0) = 0 e F ( 1) = 1.

Abordagem de cima para baixo

Neste exemplo, uma matriz de pesquisa com todos os valores iniciais é inicializada com -1. Sempre que uma solução de subproblema for necessária, ela primeiro pesquisará essa matriz de pesquisa.

Se houver o valor calculado, esse valor será retornado. Caso contrário, o resultado será calculado para armazená-lo na matriz de pesquisa, para que possa ser reutilizado posteriormente.

Foco ascendente

Nesse caso, para a mesma série de Fibonacci, f (0) é calculado primeiro, depois f (1), f (2), f (3) e assim por diante. Assim, as soluções dos subproblemas estão sendo construídas de baixo para cima.

Referências

  1. Vineet Choudhary (2020). Introdução à programação dinâmica. Desenvolvedor Insider.Taken from: developerinsider.co.
  2. Alex Allain (2020). Programação dinâmica em C ++. C Programação. Retirado de: cprogramming.com.
  3. Depois da Academia (2020). Idéia de Programação Dinâmica. Retirado de: afteracademy.com.
  4. Aniruddha Chaudhari (2019). Programação dinâmica e recursão | Diferença, vantagens com o exemplo. Pilha CSE. Retirado de: csestack.org.
  5. Code Chef (2020). Tutorial para programação dinâmica. Retirado de: codechef.com.
  6. Programiz (2020). Programaçao dinamica. Retirado de: programiz.com.

Deixe um comentário

Este site usa cookies para lhe proporcionar a melhor experiência de usuário. política de cookies, clique no link para obter mais informações.

ACEPTAR
Aviso de cookies