Programação Dinâmica

Programação dinâmica (PD; em inglês: dynamic programming, DP) é um método para resolver problemas complexos de otimização, baseado na decomposição do problema original em uma sequência de subproblemas mais simples. O método é aplicado a processos de tomada de decisão multiestágio, onde a solução ótima para o problema inteiro pode ser construída a partir das soluções ótimas de seus subproblemas.

O termo foi introduzido pelo matemático americano Richard Bellman na década de 1950. Nesse contexto, a palavra "programação" é usada no sentido de "planejamento" ou "elaboração de um plano de ação ótimo", e não na escrita de código de computador.

Propriedades e Teoremas Fundamentais

A aplicabilidade da programação dinâmica a um problema é determinada pela presença de duas propriedades fundamentais.

Princípio da Otimalidade de Bellman

O conceito central do método é o princípio da otimalidade de Bellman (em inglês: Bellman's principle of optimality). Ele afirma que: quaisquer que sejam o estado inicial e a decisão inicial, as decisões subsequentes devem constituir uma estratégia ótima em relação ao estado resultante da primeira decisão.

Em outras palavras, qualquer parte de uma trajetória ótima é, por si só, ótima. Essa propriedade permite decompor o problema geral em uma sequência de subproblemas mais simples e resolvê-los recursivamente.

Subproblemas sobrepostos

Um problema possui a propriedade de subproblemas sobrepostos (em inglês: overlapping subproblems) se, ao resolvê-lo recursivamente, os mesmos subproblemas surgem repetidamente. A PD evita cálculos repetidos, armazenando as soluções de subproblemas já encontrados (essa técnica é chamada de memoização ou tabulação), o que aumenta significativamente a eficiência em comparação com uma busca recursiva ingênua.

Equação de Bellman

Do princípio da otimalidade deriva a principal relação de recorrência do método — a equação de Bellman. Ela relaciona o "valor" (ganho ou custo ótimo) do estado atual com os valores dos estados subsequentes. Em sua forma geral, para um processo determinístico multiestágio com uma função objetivo aditiva, ela tem a seguinte aparência:

$V_{k-1}(x)=\underset{y\in U(x)}{max}\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

onde:

• $k$ — número da etapa (de $m$ a 1);
• $x$ — estado do sistema na etapa $k-1$;
• $y$ — decisão de controle tomada na etapa $k$;
• ${\phi }_k(x,y)$ — ganho (ou custo) na k-ésima etapa;
• $f_k(x,y)$ — função que define o novo estado do sistema;
• $V_k(s)$ — valor ótimo da função objetivo para o subproblema que começa na etapa $k$ no estado $s$.

A equação é resolvida sequencialmente, geralmente "de trás para frente", movendo-se da última etapa para a primeira.

Exemplos de Aplicação

• Problema do caminho mais curto em um grafo: Este problema possui a propriedade de subestrutura ótima, pois qualquer segmento de um caminho mais curto é, por si só, um caminho mais curto. Os algoritmos de Bellman-Ford e Floyd-Warshall são exemplos clássicos da aplicação da PD para resolver este problema.
• Problema da mochila: O problema de encher otimamente uma mochila de capacidade limitada com itens de diferentes valores e pesos. A PD permite resolver este problema considerando os itens sequencialmente e calculando, a cada etapa, o valor máximo para todos os valores possíveis de capacidade restante.
• Problema de alocação de recursos: A alocação de um recurso limitado (por exemplo, investimentos) entre vários projetos para maximizar o efeito geral.

Limitações

A principal limitação do método é a maldição da dimensionalidade (em inglês: curse of dimensionality) — um termo introduzido por Bellman para descrever o crescimento exponencial do número de estados e, consequentemente, da complexidade computacional, com o aumento do número de variáveis que descrevem o estado do sistema. Isso limita a aplicação prática da PD exata para problemas de dimensão muito grande.

Conceitos Relacionados

• Pesquisa Operacional
• Teoria do controle ótimo
• Processo de decisão de Markov (generalização estocástica)
• Equação de Hamilton-Jacobi-Bellman (análogo para tempo contínuo)