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
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
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]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)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}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
Bellman, R. (1957). Dynamic Programming. Princeton University Press.
ISBN: 978-0-691-07951-6Copiado.