Estruturas de dados - programação dinâmica

A abordagem de programação dinâmica é semelhante a dividir e conquistar, dividindo o problema em possíveis subproblemas menores e ainda menores. Mas, ao contrário de, dividir e conquistar, esses subproblemas não são resolvidos de forma independente. Em vez disso, os resultados desses subproblemas menores são lembrados e usados ​​para subproblemas semelhantes ou sobrepostos.

A programação dinâmica é usada onde temos problemas, que podem ser divididos em subproblemas semelhantes, para que seus resultados possam ser reutilizados. Principalmente, esses algoritmos são usados ​​para otimização. Antes de resolver o subproblema em mãos, o algoritmo dinâmico tentará examinar os resultados dos subproblemas resolvidos anteriormente. As soluções dos subproblemas são combinadas para alcançar a melhor solução.

Então, podemos dizer que -

  • O problema deve ser capaz de ser dividido em subproblemas menores de sobreposição.

  • Uma solução ótima pode ser alcançada usando uma solução ótima de subproblemas menores.

  • Algoritmos dinâmicos usam Memoização.

Comparação

Em contraste com os algoritmos gulosos, onde a otimização local é abordada, os algoritmos dinâmicos são motivados para uma otimização geral do problema.

Em contraste com os algoritmos de dividir e conquistar, onde as soluções são combinadas para alcançar uma solução geral, os algoritmos dinâmicos usam a saída de um subproblema menor e então tentam otimizar um subproblema maior. Algoritmos dinâmicos usam Memoização para lembrar a saída de subproblemas já resolvidos.

Exemplo

Os seguintes problemas de computador podem ser resolvidos usando abordagem de programação dinâmica -

  • Série de números de Fibonacci
  • Problema de mochila
  • Torre de Hanói
  • Caminho mais curto para todos os pares por Floyd-Warshall
  • Caminho mais curto por Dijkstra
  • Agendamento de projeto

A programação dinâmica pode ser usada de cima para baixo e de baixo para cima. E, claro, na maioria das vezes, consultar a saída da solução anterior é mais barato do que recomputar em termos de ciclos de CPU.