Princípios -chave da programação dinâmica (DP)

A programação dinâmica é uma técnica algorítmica usada para resolver problemas de otimização, dividindo -os em subproblemas menores e sobrepostos, resolvendo cada subproblema apenas uma vez e armazenando os resultados para evitar cálculos redundantes. É particularmente adequado para problemas que exibem subestrutura ideal e Subproblemas sobrepostos .

Aqui está um colapso de seus principais princípios:

1. subestrutura ideal:
- Um problema exibe subestrutura ideal se uma solução ideal para o problema puder ser construída de soluções ideais para seus subproblemas. Isso significa que, se você souber a solução ideal para cada peça menor, poderá montá -las para formar a solução ideal geral.
- Exemplo: O caminho mais curto entre duas cidades em um gráfico possui subestrutura ideal. Qualquer sub-caminho do caminho mais curto também deve ser o caminho mais curto entre seus pontos de extremidade.

2. Subproblemas sobrepostos:
- O problema pode ser dividido em subproblemas que são reutilizados várias vezes no cálculo. Isso significa que os mesmos subproblemas são resolvidos repetidamente se uma abordagem recursiva ingênua for usada.
- Exemplo: O cálculo do número de fibonacci envolve recursivamente o cálculo repetidamente de números de fibonacci (por exemplo, FIB (3) é calculado várias vezes ao calcular o FIB (5)).

3. Memoização (de cima para baixo) ou tabulação (de baixo para cima):
- Memoização (de cima para baixo): Essa abordagem começa com o problema original e o divide recursivamente em subproblemas. Os resultados de cada subproblema resolvido são armazenados (geralmente em um mapa de dicionário ou hash) para evitar a recomputação. Quando um subproblema é encontrado pela segunda vez, seu resultado armazenado é simplesmente procurado e devolvido.
- Tabulação (de baixo para cima): Essa abordagem calcula sistematicamente as soluções para todos os subproblemas possíveis de maneira de baixo para cima, começando com os menores subproblemas e construindo até o problema original. Os resultados geralmente são armazenados em uma tabela (por exemplo, uma matriz ou matriz).

4. estado:
- Um estado representa uma configuração específica do problema que precisa ser resolvido. Definir o estado é crucial para projetar uma solução DP. O Estado deve capturar todas as informações necessárias para resolver um subproblema independentemente de outros subproblemas. O número de estados normalmente determina a complexidade espacial da solução DP.
- Exemplo: No problema da mochila, um estado pode ser definido como `(índice, capacidade)` onde `index` representa os itens considerados até agora e a` capacidade 'representa a capacidade restante da mochila.

5. transições:
- As transições são as regras que descrevem como calcular a solução para um determinado estado com base nas soluções para seus subproblemas. Essas regras definem a relação entre os diferentes estados e permitem que você construa a solução a partir de subproblemas menores. As transições são normalmente expressas como equações recursivas.
- Exemplo: Na sequência de Fibonacci, a transição é `fib (n) =fib (n-1) + fib (n-2)`.

Aplicações de programação dinâmica

A programação dinâmica é usada extensivamente em vários domínios. Aqui estão algumas aplicações notáveis:

1. Problemas de otimização:

* Algoritmos de caminho mais curto:
* algoritmo Floyd-Warshall: Encontra os caminhos mais curtos entre todos os pares de vértices em um gráfico ponderado.
* Algoritmo Bellman-Ford: Encontra o caminho mais curto de um vértice de origem para todos os outros vértices em um gráfico ponderado, mesmo com pesos negativos da borda (detecta ciclos negativos).
* Problema de mochila: Determina os itens mais valiosos a serem incluídos em uma mochila sem exceder sua capacidade de peso. Variações incluem 0/1 mochila, mochila ilimitada e mochila fracionária.
* subsequência comum mais longa (LCS): Encontra a sequência mais longa de caracteres comuns a duas ou mais cordas. Usado em bioinformática (alinhamento de sequência), comparação de arquivos e edição de texto.
* Multiplicação da cadeia da matriz: Determina a ordem ideal para multiplicar uma sequência de matrizes para minimizar o número de multiplicações escalares.
* Editar Distância (Distância Levenshtein): Calcula o número mínimo de edições (inserções, deleções, substituições) necessárias para transformar uma string em outra. Usado em verificadores ortográficos, sequenciamento de DNA e processamento de linguagem natural.
* Mudança de moeda Problema: Encontra o número mínimo de moedas necessárias para fazer uma determinada quantidade ou o número de maneiras de fazer uma determinada quantidade usando um conjunto de moedas.
* Problema de vendedor viajante (TSP) (algoritmo retenido-karp): Encontra a rota mais curta possível que visita cada cidade exatamente uma vez e retorna à cidade de origem. Embora o DP forneça uma solução * exata * para pequenas instâncias, não é prático para grandes instâncias (NP-Hard).

2. Análise de sequência:

* Alinhamento de sequência (Bioinformática): Alinhando sequências de DNA ou proteínas para identificar semelhanças e diferenças, geralmente usando algoritmos como Needleman-Wunsch (alinhamento global) e Smith-Waterman (alinhamento local).
* Modelos Hidden Markov (HMMs): Utilizado no reconhecimento de fala, processamento de linguagem natural e bioinformática para modelar dados seqüenciais. O algoritmo Viterbi, um algoritmo DP, é usado para encontrar a sequência mais provável de estados ocultos, dada uma sequência de observações.

3. Algoritmos de gráfico:

* Caminhos mais curtos para pares (Floyd-Warshall): Como mencionado acima.
* Problemas de fluxo de rede: Encontrar o fluxo máximo de uma rede de uma fonte para um coletor.

4. Teoria dos jogos:

* Encontrando estratégias ideais: Em jogos como xadrez ou tic-tac-toe, a programação dinâmica pode ser usada para determinar os movimentos ideais para um jogador.
* Algoritmo Minimax (com poda alfa-beta): Uma variante de programação dinâmica frequentemente usada no jogo para explorar possíveis estados de jogo e encontrar a melhor jogada para um jogador.

5. Visão computacional:

* Segmentação da imagem: Dividindo uma imagem em regiões ou objetos significativos. A programação dinâmica pode ser usada para otimizar o processo de segmentação.

6. Processamento de texto:

* Justificação de texto: Determinando a maneira ideal de quebrar um parágrafo de texto em linhas para minimizar a incorporação da margem direita.
* quebra de palavras: Quebrar uma sequência de personagens em palavras.

7. Sistemas de controle:

* Controle ideal: Determinando as entradas de controle que levarão um sistema de um estado para outro de maneira ideal (por exemplo, minimizando o consumo de energia).

Escolhendo entre memórias e tabulação:

* MEMO MEMOIZAÇÃO:
* Mais intuitivo e mais fácil de entender para alguns problemas.
* Calcula apenas os subproblemas que são realmente necessários.
* Pode sofrer de excesso de pilha para uma recursão muito profunda.
* Tabulação :
* Normalmente mais eficiente em termos de fatores constantes (sem sobrecarga de recursão).
* Pode calcular alguns subproblemas que não são necessários.
* Geralmente requer uma ordem cuidadosa dos cálculos para garantir que os subproblemas sejam resolvidos antes de serem necessários.

Passos para resolver um problema de programação dinâmica:

1. Defina o estado: Determine os parâmetros que identificam exclusivamente um subproblema.
2. Defina as transições: Expresse a solução para um subproblema em termos das soluções para subproblemas menores.
3. Identifique os casos básicos: Defina as soluções para os menores subproblemas (o ponto de partida).
4. Implementar o algoritmo: Use memórias (de cima para baixo) ou tabulação (de baixo para cima) para calcular e armazenar as soluções.
5. Determine a ordem da computação: Se estiver usando a tabulação, determine a ordem correta para calcular os subproblemas.
6. Extrair a solução ideal: Depois que todos os subproblemas forem resolvidos, extraia a solução ideal para o problema original dos resultados armazenados.

A programação dinâmica é uma técnica poderosa, mas requer análise cuidadosa e design específico do problema. Compreender os princípios e praticar com vários exemplos é essencial para dominar essa abordagem algorítmica.