Programa O Dinamica

Programação
Dinâmica

Uma Metodologia de Resolução de problemas Definição (adaptado de NIST-DADSP
Uma técnica algorítmica, normalmente usada em problemas de otimização, que é baseada em guardar os resultados de subproblemas, em vez de os recalcular.
Técnica algorítmica: método geral para resolver problemas que têm algumas características em comum Problema de otimização: quando se pretende encontrar a “melhor” solução entre todas as soluções admissíveis, mediante um determinado critério (função objetivo).

Introdução
Resolve Problemas Combinando as Soluções de
Subproblemas

Aplicado quando os subproblemas não são independentes, isto é, quando os subproblemas compartilham subproblemas
Resolve cada subproblema somente uma vez e grava a resposta em uma tabela, evitando assim o trabalho de recalcular a resposta toda a vez que o subproblema é encontrado

Em geral, a Programação Dinâmica é aplicada em problemas de Otimização
Problemas de
Otimização

Muitas
Soluções
possíveis

Cada solução tem um valor

Encontrar um valor ótimo
(máximo ou
Mínimo)

O desenvolvimento de um algoritmo de programação
Dinâmica pode ser desmembrado em:

Caracterizar a estrutura de uma solução ótima
Definir recursivamente o valor de uma solução ótima Calcular o valor de uma solução ótima em um processo bottom-up
Construir uma solução ótima a partir de informações calculadas

Princípio da Otimalidade da
Programação Dinâmica
A aplicação da Programação Dinâmica-PD baseia-se fundamentalmente naquele que é conhecido como Princípio de Otimalidade de Bellman:
“Uma política de decisões ótimas só pode ser formada por subpolíticas ótimas”:

Elementos importantes em modelos de PD:
Estágios
Inicio ou termino

Estado
Local onde ocorrera a situação

Decisão
Tomar uma decisão admissível

Custos elementares da tomada e decisão
Qual valor será gasto
Critério ou Objetivo
Como minimizar o custo de uma viajem

Estilos de Resoluções de PD
- Backward: fixar o último estado = objetivo estabelecido - uso em