DAA - Programação Dinâmica
A Programação Dinâmica também é usada em problemas de otimização. Como o método dividir e conquistar, a Programação Dinâmica resolve problemas combinando as soluções de subproblemas. Além disso, o algoritmo de Programação Dinâmica resolve cada subproblema apenas uma vez e salva sua resposta em uma tabela, evitando assim o trabalho de recalcular a resposta todas as vezes.
Duas propriedades principais de um problema sugerem que o problema determinado pode ser resolvido usando a Programação Dinâmica. Essas propriedades sãooverlapping sub-problems and optimal substructure.
Subproblemas sobrepostos
Semelhante à abordagem Dividir e Conquistar, a Programação Dinâmica também combina soluções para subproblemas. É usado principalmente onde a solução de um subproblema é necessária repetidamente. As soluções calculadas são armazenadas em uma tabela, para que não tenham que ser recalculadas. Conseqüentemente, essa técnica é necessária quando existe subproblema sobreposto.
Por exemplo, a pesquisa binária não tem subproblemas de sobreposição. Considerando que o programa recursivo de números de Fibonacci tem muitos subproblemas sobrepostos.
Subestrutura Ótima
Um dado problema possui uma Propriedade de Subestrutura Ótima, se a solução ótima do problema dado pode ser obtida usando soluções ótimas de seus subproblemas.
Por exemplo, o problema do caminho mais curto tem a seguinte propriedade de subestrutura ideal -
Se um nó x encontra-se no caminho mais curto de um nó de origem u para o nó de destino v, então o caminho mais curto de u para v é a combinação do caminho mais curto de u para x, e o caminho mais curto de x para v.
Os algoritmos padrão de caminho mais curto de todos os pares, como Floyd-Warshall e Bellman-Ford, são exemplos típicos de programação dinâmica.
Etapas da abordagem de programação dinâmica
O algoritmo de programação dinâmica é projetado usando as quatro etapas a seguir -
- Caracterize a estrutura de uma solução ótima.
- Defina recursivamente o valor de uma solução ótima.
- Calcule o valor de uma solução ideal, normalmente de forma ascendente.
- Construa uma solução ótima a partir das informações computadas.
Aplicações da abordagem de programação dinâmica
- Multiplicação em cadeia de matriz
- Subsequência Comum Mais Longa
- Problema do caixeiro viajante