Skip to content
Voltar aos resultados

Programação Dinâmica

Proposto por
Richard Bellman
Ano
1957
Tipo
Exact combinatorial optimization via recursive decomposition
Família
Mathematical programming

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

Programação Dinâmica (PD) é uma técnica de otimização exata introduzida por Richard Bellman em 1957 para resolver problemas de decisão multiestágio.

Ela decompõe um problema complexo em subproblemas mais simples e sobrepostos, resolve cada subproblema uma vez e armazena os resultados para evitar computação redundante. Fundamentada no Princípio da Otimidade, a PD garante soluções globalmente ótimas sempre que o problema exibe subproblemas sobrepostos e subestrutura ótima.

A intuição por trás do método

Imagine planejar a rota mais curta através de uma cidade, encontrando primeiro os caminhos mais curtos entre cada par de interseções próximas, e depois combinando essas pequenas soluções para cima. Em vez de reexplorar todas as rotas completas possíveis do zero, você reutiliza respostas locais pré-computadas. A Programação Dinâmica funciona da mesma maneira: ela armazena em cache soluções de pequenos subproblemas para que a construção da resposta completa exija apenas consultas à tabela em vez de computações pesadas repetidas.

História

Richard Bellman cunhou o termo 'programação dinâmica' em 1957 enquanto trabalhava na RAND Corporation, escolhendo deliberadamente a palavra 'programação' para se referir a planejamento em vez de codificação de computador. O Princípio da Otimidade que ele declarou tornou-se a base teórica para a teoria de controle, pesquisa operacional e, posteriormente, aprendizado por reforço. Algoritmos clássicos de PD — o caminho mais curto de Dijkstra, o algoritmo de Viterbi e o alinhador de sequência de Needleman-Wunsch — derivam diretamente da estrutura de Bellman.

Quando usar

A Programação Dinâmica é apropriada quando um problema tem subproblemas sobrepostos e subestrutura ótima — propriedades comuns na tomada de decisão sequencial, alocação de recursos, escalonamento e tarefas de alinhamento de strings. Ela requer que o espaço de estados seja totalmente enumerável e de tamanho gerenciável; o método sofre com a maldição da dimensionalidade quando as variáveis de estado são muitas ou contínuas. Para problemas com espaços de estados intratáveis, PD aproximada ou aprendizado por reforço são alternativas preferíveis.

Limitações e considerações

  • Sofre com a maldição da dimensionalidade: requisitos de memória e tempo crescem exponencialmente com o número de variáveis de estado.
  • Requer conhecimento prévio completo da estrutura de transição e função de recompensa; inaplicável a ambientes desconhecidos sem aproximação.
  • O espaço de estados deve ser discreto ou discretizável; problemas contínuos de alta dimensão exigem esquemas de aproximação que sacrificam a exatidão.
  • Formular a representação de estado e a relação de recorrência corretas requer um insight substancial específico do problema.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Garante soluções exatas globalmente ótimas para problemas que satisfazem o Princípio da Otimidade.
  • Elimina computação redundante via memoização, alcançando tempo polinomial no número de estados.
  • Produz uma política ótima explícita, não apenas um valor ótimo, permitindo suporte direto à decisão.
  • Ampla aplicabilidade em domínios incluindo teoria de controle, bioinformática, economia e pesquisa operacional.

Aplicações

  • Problemas de caminho mais curto e roteamento em redes (variantes de Bellman-Ford, Dijkstra).
  • Alinhamento de sequências em biologia computacional (algoritmos de Needleman-Wunsch, Smith-Waterman).
  • Alocação ótima de recursos e problemas combinatórios do tipo mochila em pesquisa operacional.
  • Reconhecimento de fala e escrita manual via algoritmo de Viterbi em Modelos de Markov Ocultos.
  • Controle ótimo e otimização de portfólio multiperíodo em economia e engenharia.

Como funciona

Como funciona

1

O problema geral de otimização é expresso como uma relação de recorrência. Para cada estado s e estágio de decisão n, a função de valor V_n(s) é igual à recompensa imediata ótima mais o valor descontado do estado subsequente resultante. Essa equação de Bellman formaliza o Princípio da Otimidade: qualquer sub-caminho de um caminho ótimo deve ser ele próprio ótimo.

Fórmula
V_n(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V_{n-1}(T(s,a)) \right]
2

A recorrência é resolvida iterativamente ou recursivamente. Na iteração de valor, V^*(s) é atualizado repetidamente em todos os estados até a convergência, usando a estimativa atual dos valores dos estados vizinhos. Cada atualização substitui o valor antigo pela melhor recompensa alcançável mais o valor futuro, propagando informações de otimalidade através do espaço de estados.

Fórmula
V^*(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V^*(s') \right], \quad s' = T(s,a)
3

Valores computados são armazenados em uma tabela indexada pelo estado. Estados terminais recebem um valor base de zero (ou uma recompensa conhecida), e todas as outras entradas são preenchidas à medida que os subproblemas são resolvidos. A memoização garante que cada estado seja avaliado no máximo uma vez, reduzindo a busca recursiva exponencial para tempo polinomial no número de estados e estágios.

Fórmula
\text{Table}[s] = \begin{cases} 0 & \text{if } s \in S_{\text{terminal}} \\ V^*(s) & \text{otherwise} \end{cases}
4

Uma vez que a tabela de valores esteja completa, a política ótima pi^*(s) é recuperada por uma simples passagem gulosa: para cada estado, selecione a ação que maximiza a recompensa imediata mais o valor armazenado do estado sucessor. Essa extração em uma única passagem é computacionalmente barata e produz uma regra de decisão determinística e globalmente ótima.

Fórmula
\pi^*(s) = \arg\max_{a \in A(s)} \left[ r(s,a) + \gamma \, \text{Table}[T(s,a)] \right]

Erros comuns

  • Definir uma representação de estado insuficientemente expressiva leva a recorrências incorretas e soluções subótimas.
  • Confundir memoização top-down com tabulação bottom-up pode produzir erros de estouro de pilha ou ordenação incorreta da avaliação de subproblemas.
  • Aplicar PD a problemas que carecem de subestrutura ótima (por exemplo, caminho mais longo em um grafo geral) produz resultados incorretos sem aviso.
  • Ignorar a precisão numérica em cálculos de recompensa cumulativa pode causar erros sutis de otimalidade em implementações de ponto flutuante.

Perguntas frequentes

Qual é a diferença entre programação dinâmica e divisão e conquista?

Ambos decompõem problemas em subproblemas, mas divisão e conquista assume subproblemas independentes resolvidos apenas uma vez naturalmente. Programação dinâmica visa subproblemas sobrepostos — o mesmo subproblema aparece em múltiplos ramos — e memoriza resultados para evitar trabalho redundante. Sem subproblemas sobrepostos, PD não oferece vantagem computacional sobre recursão direta.

Quando devo usar memoização top-down versus tabulação bottom-up?

Memoização top-down é mais fácil de implementar diretamente da recorrência e computa apenas os subproblemas necessários, beneficiando espaços de estados esparsos. Tabulação bottom-up evita sobrecarga de recursão e limites de pilha, adapta-se a espaços de estados densos e é frequentemente mais rápida na prática. Escolha top-down quando o conjunto de subproblemas necessários é difícil de prever, bottom-up quando todos os subproblemas serão necessários.

Como a programação dinâmica se relaciona com o aprendizado por reforço?

PD clássica requer um modelo de Processo de Decisão de Markov totalmente conhecido (probabilidades de transição e recompensas). Aprendizado por reforço estende as ideias de PD para cenários onde o modelo é desconhecido, usando experiência amostrada em vez disso. Algoritmos como Q-learning e métodos de gradiente de política são procedimentos de PD aproximada que aprendem funções de valor a partir da interação em vez de um modelo explícito.

Métodos relacionados

Fontes

  1. Bellman, R. (1957). Dynamic Programming. Princeton University Press.

    ISBN: 978-0-691-07951-6
    Copiado.