Programação dinâmica não é magia negra

Programação dinâmica não é magia

• Programação dinâmica é uma técnica usada para resolver problemas complexos, dividindo-os em problemas menores.
• Essa técnica é natural, e muitos algoritmos comuns são aplicações de programação dinâmica a problemas específicos.
• Para ajudar a entender programação dinâmica, o texto oferece uma introdução mais fácil e uma explicação detalhada.

Reclamação

• Engenharia de software frequentemente é péssima em dar nomes.
• Termos como 'bootstrap', 'daemon', 'cascading style sheets', 'cookie' e 'inteligência artificial' são vagos ou podem induzir a erro.
• O termo 'programação dinâmica' também, por si só, não tem relação com algo 'dinâmico'; na prática, é uma ideia usada em projeto de algoritmos.

Cache básico

• Ao tentar resolver um problema dividindo-o em pequenos problemas parecidos, pode ser necessário resolver os mesmos subproblemas várias vezes.
• Usando a sequência de Fibonacci como exemplo, uma implementação recursiva simples repete o mesmo cálculo muitas vezes.
• É possível evitar cálculos duplicados armazenando os resultados em cache (ou usando memoização).

Cache otimizado

• Com memoização, você mantém a recursão, mas calcula cada coisa apenas quando ela é necessária.
• Em vez disso, também é possível adotar uma abordagem que calcula antecipadamente tudo o que será necessário.
• Esse método resolve o problema sem chamadas recursivas, e isso é justamente programação dinâmica.

Distância de edição

• A distância de edição entre duas strings é o número mínimo de edições necessárias para transformar uma string na outra.
• A distância de edição pode ser calculada com substituição, inserção e remoção de caracteres, e isso pode ser resolvido de forma eficiente com programação dinâmica.
• É preciso encontrar uma forma de derivar a solução completa a partir das soluções dos problemas menores.

Advent of Code, Dia 12

• No problema do Advent of Code de 12 de dezembro de 2023, é preciso resolver um nonograma 1D.
• Dá para resolver por força bruta, mas isso tem complexidade exponencial.
• Em vez disso, é possível aplicar programação dinâmica para resolver de forma eficiente.

Conclusão

• Programação dinâmica não é fácil, mas também não está fora do alcance da maioria dos programadores.
• Se você entender como dividir um problema em problemas menores, poderá usar memoização em várias situações, o que representa uma grande melhoria em relação a implementações ingênuas.
• Ao dominar programação dinâmica, você passa a entender toda uma classe de algoritmos, compreende melhor os trade-offs e abre caminho para outras otimizações.

Opinião do GN⁺

• Programação dinâmica é uma técnica importante para resolver problemas complexos com eficiência, reduzindo cálculos redundantes ao armazenar em cache as soluções dos subproblemas em vez de recalculá-las com uma abordagem puramente recursiva.
• Este artigo é muito útil para engenheiros de software iniciantes que querem entender os conceitos básicos de programação dinâmica.
• Os exemplos de sequência de Fibonacci e distância de edição ajudam a compreender o conceito de programação dinâmica e oferecem um bom ponto de partida para aplicá-lo na resolução de problemas reais.

[GN⁺]

Comentários do Hacker News

• O fato de o artigo explicar algoritmos de programação dinâmica (DP) como cache para recursão é um ponto positivo.

  • Encontrar uma solução recursiva é um ótimo ponto de partida para encontrar uma solução de DP.
  • Aplicar memoization a uma solução recursiva pode ajudar bastante a melhorar o desempenho.
  • O importante não é haver um grande número de subproblemas na árvore de chamadas, mas sim um número relativamente pequeno de subproblemas distintos.

• Gostou da forma como o artigo primeiro trata o problema de maneira recursiva, depois adiciona cache gradualmente e por fim reduz o cache ao tamanho necessário.

  • Já passou pela experiência de tentar encontrar diretamente uma solução de programação dinâmica e acabar travando ou exigindo muito esforço.
  • Daqui para frente, pretende se forçar a seguir uma abordagem em ordem.

• Uma das aplicações mais interessantes de programação dinâmica é o alinhamento pareado de sequências de ácidos nucleicos/proteínas.

  • Por exemplo, há alinhamento de sequências, o algoritmo de Needleman–Wunsch e o algoritmo de Smith–Waterman.

• Compartilha uma experiência com um professor de algoritmos excepcional.

  • O professor estudou na UCLA, e sua aula sobre programação dinâmica foi excelente.
  • Ele começou com um problema simples, mas com complexidade exponencial, dividiu o problema em problemas menores e reduziu a complexidade para polinomial, depois aplicou memoization e a derrubou para complexidade linear.
  • Gostaria de lembrar quais problemas foram usados.

• Compartilha um link para o texto Programação dinâmica não é magia negra.

  • O texto ficou difícil de acessar por causa de muito tráfego (hug of death).

• Diz que, por ter aprendido programação principalmente sozinho, provavelmente não saberia o que fazer se numa entrevista de emprego pedissem para usar programação dinâmica.

  • Felizmente isso nunca aconteceu, e conhecer a técnica ajudou em várias entrevistas.

• O nome "programação dinâmica" pode não parecer vir da área de programação.

  • Na verdade, está relacionado à otimização e é um método para resolver problemas de decisão em tempo discreto.
  • Programação dinâmica é uma forma de reduzir bastante a dimensão de um problema de otimização definindo a função valor V*.

• Levanta a dúvida se é errado pensar apenas em "memoization" quando se ouve "programação dinâmica".

  • Talvez a parte que falte seja dividir o problema de forma inteligente para conseguir usar memoization com eficiência.

• Programação dinâmica não é magia negra; o difícil é provar que algo pode ser programado dinamicamente e demonstrar sua correção.

  • Assim como nos algoritmos gulosos, é necessária uma prova formal usando indução matemática.

• Para dominar programação dinâmica, recomenda o livro de algoritmos DPV e o curso da Udacity do Georgia Tech.

  • Dá para aprender programação dinâmica praticando a resolução de problemas.