Programação Dinâmica

Programação dinâmica é um paradigma de design de algoritmos que resolve problemas com subestrutura ótima e subproblemas sobrepostos, resolvendo cada subproblema uma vez e armazenando seu resultado para reutilização, transformando a recomputação exponencial em computação de tempo polinomial.

Definition

Programação dinâmica é um método que resolve um problema de otimização ou contagem definindo seu valor recursivamente em termos de subproblemas sobrepostos e computando cada subproblema distinto exatamente uma vez, armazenando em cache o resultado para que possa ser reutilizado em vez de recomputado.

Scope

Este tópico abrange as duas características que tornam a programação dinâmica aplicável — subestrutura ótima e subproblemas sobrepostos — e os dois estilos de implementação, memoização top-down e tabulação bottom-up. Inclui problemas canônicos como a subsequência comum mais longa, distância de edição, problema da mochila, multiplicação de cadeia de matrizes e programas dinâmicos de caminho mais curto, juntamente com o design do espaço de estados e a análise das compensações de tempo e espaço. Exclui métodos de caminho mais curto específicos de grafos tratados em algoritmos de grafos, embora compartilhem o mesmo princípio subjacente.

Core questions

• O problema possui subestrutura ótima que permite que uma solução ótima seja construída a partir de subsoluções ótimas?
• Como o conjunto de subproblemas (o espaço de estados) é definido para que cada um se repita apenas um número polinomial de vezes?
• A solução deve ser implementada de cima para baixo com memoização ou de baixo para cima com tabulação?
• Como a tabela pode ser reconstruída para recuperar a solução ótima real, e não apenas seu valor?
• Como o espaço pode ser reduzido quando apenas parte da tabela é necessária em cada etapa?

Key concepts

• subestrutura ótima
• subproblemas sobrepostos
• princípio da otimalidade
• memoização
• tabulação
• espaço de estados e recorrência
• subsequência comum mais longa
• distância de edição
• problema da mochila

Key theories

Princípio da otimalidade

O princípio da otimalidade de Bellman afirma que uma política ótima tem a propriedade de que, quaisquer que sejam o estado inicial e a decisão, as decisões restantes devem constituir uma política ótima para o estado resultante — a base formal das recorrências da programação dinâmica.

Memoização versus tabulação

Um programa dinâmico pode ser realizado de cima para baixo adicionando um cache a uma formulação recursiva (memoização) ou de baixo para cima preenchendo uma tabela em ordem de dependência (tabulação); ambos computam cada subproblema uma vez, mas diferem na ordem de avaliação e no comportamento do espaço.

Clinical relevance

A programação dinâmica é onipresente na prática: alinhamento de sequências (Needleman-Wunsch, Smith-Waterman) em biologia computacional, distância de edição em verificação ortográfica e diferenças de controle de versão, o algoritmo de Viterbi em reconhecimento de fala e comunicações, e programas dinâmicos em pesquisa operacional, finanças e aprendizado por reforço.

History

Richard Bellman desenvolveu a programação dinâmica na década de 1950 enquanto estava na RAND Corporation, escolhendo o nome em parte para ser palatável aos patrocinadores da pesquisa. O princípio da otimalidade e a equação de Bellman tornaram-se fundamentais na pesquisa operacional, teoria de controle e ciência da computação, e a técnica foi posteriormente codificada como um paradigma algorítmico central em livros didáticos de algoritmos.

Key figures

• Richard Bellman
• Thomas H. Cormen
• Jon Kleinberg
• Éva Tardos

Seminal works

• bellman1957
• cormen2009

Frequently asked questions

Qual é a diferença entre dividir para conquistar e programação dinâmica?

Ambos decompõem um problema em subproblemas, mas os subproblemas de dividir para conquistar são independentes e resolvidos uma vez, enquanto os subproblemas de programação dinâmica se sobrepõem e seriam recomputados muitas vezes por recursão ingênua. A programação dinâmica armazena em cache as soluções de subproblemas para evitar essa recomputação.

Quando a programação dinâmica não se aplica?

Ela requer subestrutura ótima e um conjunto de subproblemas distintos de tamanho polinomial. Se o problema não possui subestrutura ótima, ou se o espaço de estados natural é exponencial e não pode ser comprimido, a programação dinâmica é incorreta ou não é mais eficiente.