Quais as vantagens e desvantagens da programação dinâmica para resolução de problemas de otimização operacional?

Essa página foi indicada para eliminação rápida pela regra: Artigo de Wikipédia Proponente: Albertoleoncio (discussão) 12h55min de 4 de maio de 2022 (UTC) A página será eliminada por um administrador se estiver em conformidade com a regra

Desafio 3.0 - Pesquisa Operacional - Cláudio Aroucha

Elaborado por: Lucas Coelho, Victor Cunha, e Agno Nunes

Programação dinâmica

Programação dinâmica é um método para a construção de algoritmos para a resolução de problemas computacionais, em especial os de otimização combinatória. [1]Ela é aplicável a problemas nos quais a solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada - de forma a evitar recálculo - de outros subproblemas que, sobrepostos, compõem o problema original. O que um problema de otimização deve ter para que a programação dinâmica seja aplicável são duas principais características: subestrutura ótima e superposição de subproblemas. Um problema apresenta uma subestrutura ótima quando uma solução ótima para o problema contém em seu interior soluções ótimas para subproblemas. A superposição de subproblemas acontece quando um algoritmo recursivo reexamina o mesmo problema muitas vezes.

Exemplo Sequência de Fibonacci

Como exemplo simples de programação dinâmica, com alguma frequência, alguns textos, utilizam a determinação da Sequência de Fibonacci, quando implementada de forma recursiva. Isso porque quando a forma recursiva é implementada sem maiores cuidados, sem memorização, o seu cálculo de tempo cresce exponencialmente.

• 

  Exemplo Sequência de Fibonacci

Quando implementada de forma recursiva "ingênua" (naïve), sem memorização, a dupla chamada a F na segunda linha causa a necessidade da repetição de cálculos, que cresce exponencialmente.

Vantagens e Desvantagens

Quando você começa a trabalhar com mais de um sistema, pode correr uma série de conflitos devido ao uso de algoritmos recursivos, que reexaminam o mesmo problema muitas vezes, e nesta situação, gerando novos conflitos e bugs.

Para resolver esses problemas, existe a programação dinâmica, que se trata de uma metodologia de construção de algoritmos que resolvam problemas originais do sistema, de forma que otimize e faça uso da análise combinatória, afim de prevenir queda de performance e recálculos desnecessários para atender subsistemas que possam sobrepujar o sistema original, gerando novos subproblemas.

Ou seja, quando você começar a programar, o ideal é você pensar em abstrair o máximo que puder para que não ocorra problemas no futuro, isso é um pensamento dinâmico.

A Programação Dinâmica pode ser caracterizada como um processo sequencial de tomada de decisões. Nela não existe uma formulação matemática, como ocorre na Programação Linear.

Como vantagens se destacam:

• Pode ser utilizada num grande número de problemas de otimização discreta;
• Não necessita de muita precisão numérica;
• Útil para aplicar em problemas que exigem teste de todas as possibilidades.

Já como desvantagens temos:

• Necessita de grande espaço de memória;
• A complexidade espacial pode ser exponencial.

Referências

- Dasgupta, Sanjoy (2009). Algoritmos. São Paulo: McGraw Hill

- Cormen, Thomas (2009). Algoritmos: Teoria e Prática 3 ed. [S.l.]: Campus.

tenha um ótimo dia :3