PROGRAMAÇÃO DINÂMICA E ANÁLISE DE DECISÃO

PROGRAMAÇÃO DINÂMICA

DEFINIÇÃO
É uma técnica algorítmica, normalmente usada em problemas de optimização, que é baseada em guardar os resultados de subproblemas, em vez de os recalcular.
Muitos algoritmos eficientes seguem o paradigma da programação dinâmica. Esse paradigma, ou estratégia de projeto de algoritmos, é uma espécie de tradução iterativa inteligente da recursão e pode ser definido, vagamente, como recursão com apoio de uma tabela.
Como em um algoritmo recursivo, cada instância do problema é resolvida a partir da solução de instâncias menores, ou melhor, de subinstâncias da instância original. A característica distintiva da programação dinâmica é a tabela que armazena as soluções das várias subinstâncias. O consumo de tempo do algoritmo é, em geral, proporcional ao tamanho da tabela.

CARACTERÍSTICAS DE UM PROBLEMA DE PROGRAMAÇÃO DINÂMICA
- Subestrutura óptima (“optimal substructure”): Quando a solução óptima de um problema contém nela própria soluções óptimas para subproblemas do mesmo tipo.
- Subproblemas coincidentes: Quando um espaço de subproblemas é pequeno, isto é, não são muitos os subproblemas a resolver pois muitos deles são exactamente iguais uns aos outros.

METODOLOGIA DE RESOLUÇÃO
1) Caracterizar a solução óptima do problema
• Compreender bem o problema
• Verificar se um algoritmo que verifique todas as soluções à força bruta não é suficiente.
• Tentar generalizar o problema (é preciso prática para perceber como generalizar da maneira correta).
• Procurar dividir o problema em subproblemas do mesmo tipo.
• Verificar se o problema obedece ao princípio de optimalidade.
• Verificar se existem subproblemas coincidentes

2) Definir recursivamente a solução óptima, em função de soluções óptimas de subproblemas.
Definir recursivamente o valor da solução óptima, com rigor e exactidão, a partir de subproblemas mais pequenos do mesmo tipo.
• Imaginar sempre que os valores das soluções óptimas já estão disponíveis quando