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

Grupo de Usuários Wiki Movimento Brasil
Ir para navegação Ir para pesquisar
Rapid delete.svg 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)
[responder]

A página será eliminada por um administrador se estiver em conformidade com a regra

Desafio 3.0 - Pesquisa Operacional - Cláudio Aroucha[editar]

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

Programação dinâmica[editar]

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[editar]

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.


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[editar]

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[editar]

- 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