Técnica Top-Down e Bottom-Up na programação dinâmica §

---

Abstract

Programação dinâmica é uma técnica que resolve problemas de otimização ao dividir o problema em subproblemas menores, armazenando soluções intermediárias para evitar cálculos redundantes. Suas abordagens principais são as estratégias bottom-up (iterativa) e top-down (recursiva com memoização).

Introdução §

Muitos problemas computacionais envolvem a solução de subproblemas repetidos. Para lidar com isso de maneira eficiente, programação dinâmica (PD) utiliza uma abordagem estruturada: ela resolve cada subproblema uma única vez, armazenando seus resultados para evitar recalcular.

As duas principais técnicas de implementação em programação dinâmica são:

1. Top-Down: Uma abordagem recursiva com memoização, que resolve subproblemas conforme necessário, armazenando seus resultados.
2. Bottom-Up: Uma abordagem iterativa que resolve subproblemas menores antes de resolver subproblemas maiores, construindo uma solução de maneira incremental.

Ambas as técnicas compartilham a mesma ideia central, mas diferem em como o problema é processado e estruturado.

Definição §

Programação dinâmica é uma técnica de otimização que utiliza a sobreposição de subproblemas e a subestrutura ótima.

• Sobreposição de Subproblemas: Os mesmos subproblemas aparecem repetidamente durante a solução do problema.
• Subestrutura Ótima: A solução ótima para um problema pode ser construída a partir das soluções ótimas de seus subproblemas.

Seja um problema descrito por uma função de estado , a relação de recorrência expressa como:

onde representa o custo de uma decisão e descreve como o estado é alterado pela decisão, captura a essência de muitos problemas resolvidos por programação dinâmica.

Estratégias §

1. Top-Down:

   • Começa com o problema maior e divide recursivamente em subproblemas menores.
   • Usa memoização para armazenar os resultados já calculados.
   • Evita cálculos redundantes durante a recursão.

2. Bottom-Up:

   • Resolve os subproblemas menores primeiro, armazenando os resultados.
   • Utiliza tabelas para organizar as soluções intermediárias.
   • É implementada iterativamente, evitando o overhead de chamadas recursivas.

Detalhamento das Técnicas §

Top-Down: Recursão com Memoização §

Na estratégia top-down, a função é chamada recursivamente para resolver subproblemas conforme necessário. Sempre que um subproblema é resolvido, seu resultado é armazenado (memoizado).

• Vantagem: Mais fácil de implementar e entender devido à estrutura recursiva.
• Desvantagem: Pode enfrentar problemas de profundidade de pilha em casos de entrada grande.

Exemplo de Implementação (Fibonacci):

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]
 
print(fib(10))  # Resultado: 55

Bottom-Up: Abordagem Iterativa §

Na abordagem bottom-up, a solução começa pelos subproblemas menores e progride iterativamente até resolver o problema maior.

• Vantagem: Não sofre problemas de profundidade de pilha e frequentemente usa menos memória que a abordagem top-down.
• Desvantagem: Requer planejamento explícito para definir a ordem de resolução dos subproblemas.

Exemplo de Implementação (Fibonacci):

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
 
print(fib(10))  # Resultado: 55

Comparação entre Top-Down e Bottom-Up §

Característica	Top-Down	Bottom-Up
Estrutura	Recursiva	Iterativa
Armazenamento	Memoização (estrutura dinâmica)	Tabela (estrutura fixa)
Facilidade de Implementação	Mais simples (para problemas recursivos)	Pode ser mais desafiador
Eficiência	Pode ser menos eficiente (overhead de recursão)	Geralmente mais eficiente

Exemplo §

Problema: Mochila Fracionária §

Considere um problema de maximizar o valor total de itens que podem ser colocados em uma mochila com capacidade fixa. Suponha que temos itens com pesos e valores conhecidos.

Abordagem Bottom-Up:

Definimos como o valor máximo que pode ser alcançado usando os primeiros itens e capacidade . A relação de recorrência é:

onde e são o peso e valor do item .

Exemplo de Implementação:

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 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][capacity]
 
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack(weights, values, capacity))  # Resultado: 7

Referências §

---