Programação Dinâmica

Algoritmos e Programação de Computadores II


Prof. MSc. Leanderson André

leandersonandre@univille.br


Universidade da Região de Joinville

Programação Dinâmica

Definição
Técnica de Design de Algoritmo que pode ser utilizada pra encontrar soluções ótima para problemas e contar o número de soluções.

Problema do Troco

Dado um conjunto de moedas = {c1,c2,…ck} e uma quantidade dinheiro alvo n, encontre a menor combinação de moedas que somados resulta na quantidade n.

Moedas do real brasileiro

Problema do Troco

Exemplo: moedas = {1,2,5}, alvo = 12.

Qual é a solução ótima?

3 moedas
5 + 5 + 2 = 12

Problema do Troco

Exemplo: moedas = {1,2,5}, alvo = 12.

Qual foi a estratégia adotada?

Selecione sempre a maior moeda sem exceder o valor da soma.
Algoritmo guloso

Problema do Troco

Exemplo: moedas = {1,3, 4}, alvo = 6.

Qual é a solução ótima?

Algoritmo guloso: 3 moedas: 4 + 1 + 1 = 6
Solução ótima: 2 moedas: 3 + 3 = 6

Problema do Troco

Algoritmos gulosos não garantem a solução ótima.

Algoritmos de força bruta garantem a solução ótima por explorar todas as possibilidades, mas podem ser muito lentos para uma grande quantidade de dados de entrada.

Qual é a alternativa?

A programação dinâmica pode encontrar a solução ótima como a força bruta mas sendo eficiente.

Procurando a solução ótima

O problema pode ser reformulado de maneira recursiva para encontrar a solução para os seus subproblemas.

Por exemplo: moedas = {1,3,4}

Expressão Valor Expressão Valor
resolver(0) 0 resolver(6) 2
resolver(1) 1 resolver(7) 2
resolver(2) 2 resolver(8) 2
resolver(3) 1 resolver(9) 3
resolver(4) 1 resolver(10) 3
resolver(5) 2

A propriedade essencial de resolver é que seus valores podem ser calculadas recursivamente para os valores menores.
Por exemplo: moedas = {1,3,4}

resolver(x) = min(resolver(x-1) + 1,
                  resolver(x-3) + 1,
                  resolver(x-4) + 1)
                  

O caso base da recursão é resolver(0) = 0.

Chamadas recursivas do algortimo

A cada nível, uma moeda é utilizada.

Chamadas recursivas do algortimo

Caminhos das soluções possíveis.

Solução

Por exemplo: moedas = {1,3,4}, soma = 10

resolver(10) = resolver(7) + 1  // x - 3
             = resolver(4) + 2  // x - 2
             = resolver(0) + 3  // x - 4     
             = 3           

Algoritmo recursivo

$$ \operatorname{resolver}(x)= \begin{cases} \infty, & x < 0 \\ 0, & x = 0 \\ \displaystyle\min_{c \in \text{moedas}} \left\{\operatorname{resolver}(x-c)+1\right\}, & x > 0 \end{cases}$$

Exercício

Codifique a solução recursiva para o problema do troco utilizando a linguagem Python.

Entrada: moedas = {1,3,4}, x = 10

Saída: 3

Solução

def resolver(soma,moedas):
    if soma < 0:
        return float('inf')
    if soma == 0:
        return 0
    menor = float('inf')
    for m in moedas:
        r = resolver(soma-m, moedas) + 1
        menor = min(menor,r)
    return menor
moedas = [1,3,4]
resultado = resolver(10,moedas)
print("Resultado:",resultado)

Memoização

A idéia chave na programação dinâmica é a memoização.

Definição
Memoização (do inglês, memoization) é uma técnica de otimização que armazena os resultados de funções para reutilizá-los em chamadas futuras, evitando recálculos desnecessários.

Aplicação da Memoização no programa do Troco

Deve-se verificar se a tabela já contêm a solução para aquela instância do problema.

Caso tiver, utilize a solução armazenada.

if soma in tabela:
    return tabela[soma]

Aplicação da Memoização no programa do Troco

Caso contrário, calcule a solução. Após identificar a melhor solução para a determinada instância do problema, armazene a solução na tabela.

def resolver(soma,moedas,tabela={}):
    if soma < 0:
        return float('inf')
    if soma == 0:
        return 0
    if soma in tabela:
        return tabela[soma]    
    menor = float('inf')
    for m in moedas:
        r = resolver(soma-m, moedas, tabela) + 1
        menor = min(menor,r) 
    tabela[soma] = menor
    return menor

Implementação iterativa

Implementação iterativa pode apresentar algumas vantagens como possuir uma implementação mais simples e uso constante de memória.

def resolver(soma,moedas):
    tabela={0:0}
    for i in range(1,soma+1):
        tabela[i] = float('inf')
        for m in moedas:
            if i-m >= 0:
              tabela[i] = min(tabela[i],tabela[i-m]+1)
    return tabela[soma]

Construindo a solução

Algumas vezes, um determinado problema solicita qual é sua a solução ótima. No problema do troco, é necessário uma estrutura de dados para armazenar a primeira moeda da solução que resolve o problema.

def resolver(soma,moedas):
    tabela={0:0}
    solucao={}
    for i in range(1,soma+1):
        tabela[i] = float('inf')
        for m in moedas:
            if i-m >= 0 and tabela[i-m]+ 1 < tabela[i]:
              tabela[i] = min(tabela[i],tabela[i-m]+1)
              solucao[i] = m
    # Imprimir no terminal neste ponto
    return tabela[soma]

Construindo a solução

Para apresentar a solução ótima no terminal.

    s = soma
    print("Solução: ",end="")
    while s > 0:
        print(solucao[s],end="")
        s -= solucao[s]
    print()

Exercícios

Contando as soluções

Dado o problema do troco, crie uma solução utilizando a programação dinâmica que retorne a quantidade de soluções válidas.

Entrada: moedas = {1 ,3, 4}, soma = 5

Saída: 6

1 + 1 + 1 + 1 + 1 3 + 1 + 1
1 + 1 + 3 1 + 4
1 + 3 +1 4 + 1

Exercícios

Longest Increasing Subsequence (LIS)

Dada uma sequência de números inteiros, encontre o tamanho da maior subsequência estritamente crescente (não necessariamente contínua). Uma subsequência é formada removendo zero ou mais elementos da sequência original, sem alterar a ordem relativa dos elementos restantes. Crie uma solução utilizando programação dinâmica para determinar o comprimento da Longest Increasing Subsequence (LIS).

Entrada: sequência = {10, 22, 9, 33, 21, 50, 41, 60}

Saída: 5

Exercícios

Longest Increasing Subsequence (LIS)

Entrada: sequência = {10, 22, 9, 33, 21, 50, 41, 60}

Saída: 5

Explicação: A maior subsequência crescente possui comprimento 5.

10 → 22 → 33 → 50 → 60
10 → 22 → 33 → 41 → 60
Univille

Prof. MSc. Leanderson André

leandersonandre@univille.br


Universidade da Região de Joinville