Noções básicas de programação dinâmica

5.1 Definição de programação dinâmica.

Programação dinâmica (Dynamic Programming, DP) é um método de otimização usado para resolver problemas complexos dividindo-os em subproblemas mais simples. A programação dinâmica é eficaz para problemas que podem ser divididos em subproblemas sobrepostos com uma estrutura ótima.

Princípios de funcionamento:

1. Subestrutura ótima:

Um problema possui uma subestrutura ótima se sua solução ótima pode ser construída a partir das soluções ótimas de seus subproblemas. Isso significa que é possível resolver um problema maior resolvendo vários subproblemas menores.

2. Subproblemas sobrepostos:

Um problema tem subproblemas sobrepostos se seus subproblemas se repetem várias vezes durante a resolução do problema. A programação dinâmica resolve efetivamente problemas com subproblemas sobrepostos, memorizando os resultados dos subproblemas já resolvidos (memoização).

3. Memoização e tabulação:

Memoização (de cima para baixo): Abordagem recursiva onde os resultados dos subproblemas são armazenados na memória para evitar cálculos repetidos.

Tabulação (de baixo para cima): Abordagem iterativa onde os resultados dos subproblemas são calculados e armazenados em uma tabela (normalmente um array) e utilizados para calcular o resultado final.

Exemplos de problemas resolvidos com programação dinâmica

5.2 Problema da mochila.

Problema:

Existe um conjunto de itens, cada um com um peso e um valor. É necessário escolher itens para uma mochila com capacidade limitada, de forma a maximizar o valor total.

Importante! Ao contrário de um problema semelhante, que pode ser bem resolvido com um algoritmo guloso, neste problema, não é possível dividir os itens.

Solução:

Uma tabela é criada, onde as linhas correspondem aos itens e as colunas à capacidade possível da mochila. O valor em uma célula representa o valor máximo para um determinado número de itens e capacidade.

Complexidade temporal: O(n * W), onde n é o número de itens e W é a capacidade da mochila.

Exemplo de código em Python:

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
            
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
            
    return dp[n][W]
        
        

5.3 Problema de encontrar o menor caminho

Problema:

Encontrar os caminhos mais curtos entre todos os pares de vértices em um gráfico ponderado.

Solução:

Usa-se uma tabela, onde as linhas e colunas correspondem aos vértices do gráfico. O valor em uma célula representa a menor distância entre dois vértices.

Complexidade temporal: O(V^3), onde V é o número de vértices

Exemplo de código em Python:

def floyd_warshall(graph):
    v = len(graph)
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
            
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
            
    return dist
        
        

5.4 Comparação da programação dinâmica com outros métodos.

Comparação com o método de força bruta (brute force):

Complexidade temporal:

• Força bruta: geralmente tem complexidade temporal exponencial (por exemplo, O(2^n) para o problema de Fibonacci).
• Programação dinâmica: reduz a complexidade temporal para polinomial (por exemplo, O(n) para o problema de Fibonacci).

Complexidade espacial:

• Força bruta: pode usar menos memória, mas os custos temporais são altos.
• Programação dinâmica: pode usar mais memória para armazenar resultados intermediários (por exemplo, O(n) para o problema de Fibonacci com memoização), mas ganha em tempo.

Comparação com o método de algoritmos gulosos (greedy algorithms):

Otimização:

• Algoritmos gulosos: nem sempre encontram a solução globalmente ótima, mas funcionam mais rápido e são mais fáceis de implementar.
• Programação dinâmica: encontra a solução globalmente ótima, mas requer mais recursos computacionais.

Exemplos de problemas:

• Algoritmos gulosos: problema da mochila fracionária (fractional knapsack), árvore geradora mínima (MST).
• Programação dinâmica: problema da mochila (inteiro), maior subsequência comum (LCS).