Programação dinâmica: características, exemplo, vantagens, desvantagens - Ciência - 2023

Contente

o programaçao dinamica É um modelo de algoritmo que resolve um problema complexo dividindo-o em subproblemas, armazenando seus resultados para evitar ter que recalcular esses resultados.

Este cronograma é usado quando você tem problemas que podem ser divididos em subproblemas semelhantes, para que seus resultados possam ser reutilizados. Na maior parte, este cronograma é usado 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 para os subproblemas são combinadas para alcançar a melhor solução.

Em vez de calcular o mesmo subproblema repetidamente, você pode armazenar sua solução em alguma memória, quando encontrar este subproblema pela primeira vez. Quando ele reaparecer durante a solução de outro subproblema, a solução já armazenada na memória será tomada.

Esta é uma ideia maravilhosa para fixar o tempo de memória, onde usando espaço adicional você pode melhorar o tempo necessário para encontrar uma solução.

Recursos de programação dinâmica

As seguintes características essenciais são o que você deve ter um problema antes que a programação dinâmica possa ser aplicada:

Subestrutura ótima

Esta característica expressa que um problema de otimização pode ser resolvido pela combinação das soluções ótimas 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 ótima será apresentada no caminho mais curto r que vai de um vértice s a um vértice t:

Ou seja, neste caminho mais curto r qualquer vértice intermediário i pode ser tomado. Se r é realmente a rota mais curta, então ela pode ser dividida nas sub-rotas r1 (de s para i) e r2 (de i para t), de forma que estas sejam por sua vez as rotas mais curtas entre os vértices correspondentes.

Portanto, para encontrar os caminhos mais curtos, a solução pode ser facilmente formulada recursivamente, que é o que o algoritmo Floyd-Warshall faz.

Subproblemas sobrepostos

O espaço do subproblema deve ser pequeno. Ou seja, qualquer algoritmo recursivo que resolva um problema terá que resolver os mesmos subproblemas continuamente, em vez de gerar novos subproblemas.

Por exemplo, para gerar a série de Fibonacci, esta formulação recursiva pode ser considerada: Fn = F (n - 1) + F (n - 2), tomando como caso base que F1 = F2 = 1. Teremos então: F33 = F32 + F31 e F32 = F31 + F30.

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

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

Abordagem de cima para baixo

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

Cada vez que uma nova solução de subproblema é procurada, a tabela será verificada para ver se ele foi 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.

Abordagem de baixo para cima

Depois que a solução de um problema é formulada recursivamente em termos de seus subproblemas, é possível tentar reformular o problema de forma ascendente: primeiro, tentaremos resolver os subproblemas e usar suas soluções para chegar a soluções para os subproblemas maiores.

Isso também é geralmente feito em forma de tabela, gerando soluções iterativamente 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 característica significativa de um problema que pode ser resolvido por meio da programação dinâmica é que ele deve ter subproblemas sobrepostos. Isso é o que distingue a programação dinâmica da técnica de dividir para conquistar, onde não é necessário armazenar os valores mais simples.

É semelhante à recursão, pois, ao calcular os casos-base, o valor final pode ser determinado indutivamente. Esta abordagem ascendente funciona bem quando um novo valor depende apenas de valores calculados anteriormente.

Exemplo

Passos mínimos para chegar a 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 for divisível por 2, é dividido por 2 (se e% 2 == 0, então e = e / 2).

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

Com base nas etapas acima, o número mínimo dessas etapas deve ser encontrado para trazer e para 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

Pode-se pensar em escolher sempre o degrau que torna n o mais baixo possível e continuar assim, até chegar a 1. Porém, percebe-se que essa estratégia não funciona aqui.

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

Tudo começa com recursão: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} se e> 1, tomando como caso base: F (1) = 0. Tendo 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 ótima para um dado input 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 na parte inferior, trabalhando seu caminho até o e fornecido. Então, ambos os códigos:

Memorização

Programação dinâmica de baixo para cima

Vantagem

Uma das principais vantagens da utilização da programação dinâmica é que ela agiliza o processamento, uma vez que são utilizadas referências previamente calculadas. Por ser uma técnica de programação recursiva, ela reduz as linhas de código do programa.

Algoritmos vorazes vs programação dinâmica

Algoritmos gananciosos são semelhantes à programação dinâmica, pois ambos são ferramentas de otimização. No entanto, o algoritmo guloso busca uma solução ótima em cada etapa local. Ou seja, busca uma escolha gananciosa na esperança de encontrar um ótimo global.

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

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

Desvantagens

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

- Muitas vezes, o valor de saída é armazenado sem nunca ser usado nos seguintes subproblemas durante a execução. Isso leva ao uso desnecessário da 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 seu código e a velocidade de processamento não for uma preocupação, você pode usar a recursão. Por exemplo, se você estiver desenvolvendo um aplicativo móvel, a memória é muito limitada para executar o aplicativo.

Se você deseja que o programa execute 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 resoluçã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 muito bem para uma ampla gama de problemas. Muitos algoritmos podem ser vistos como aplicativos de algoritmo gananciosos, como:

- Série de números de Fibonacci.

- Torres de Hanói.

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

- Problema na mochila.

- Agendamento do projeto.

- O caminho mais curto por 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 encontrados 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 a solução para um subproblema for necessária, esta matriz de pesquisa será pesquisada primeiro.

Se o valor calculado estiver lá, esse valor será retornado. Caso contrário, o resultado será calculado para ser armazenado na matriz de pesquisa para que possa ser reutilizado posteriormente.

Abordagem de baixo para cima

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

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