4.12. Programação Dinâmica¶

Muitos programas em Ciência da Computação são escritos para otimizar algum valor; por exemplo, encontre o caminho mais curto entre dois pontos, encontre a linha que melhor se encaixa em um conjunto de pontos, ou encontre o menor conjunto de objetos que satisfaz algum critério. Existem muitas estratégias que os cientistas da computação usam para resolver esses problemas. Um dos objetivos deste livro é expor você a várias estratégias diferentes de solução de problemas. A Programação Dinâmica é uma estratégia para esses tipos de problemas de otimização.

Um exemplo clássico de um problema de otimização envolve calcular o troco usando um número mínimo de moedas. Suponha que você seja um programador de um fabricante de máquinas de venda automática. Sua empresa quer ajudar seus clientes dando o menor número possível de moedas como troco para cada transação. Suponha que um cliente coloca em uma nota de um dólar e compra um item por 37 centavos. Qual é o menor número de moedas que você pode dar de troco (usando moedas de 25, 10, 5 e 1 centavos de dólar)? A resposta é seis moedas: duas de 25 centavos, uma de 10 centavos e três de 1 centavo. Como chegamos à essa resposta? Começamos com a maior moeda a nossa disposição (de 25 centavos) e usamos tantas quanto possível, então vamos para a próxima moeda de maior valor (de 10 centavos) e usamos o maior número possível delas. Esta primeira abordagem é chamada de método guloso porque tenta resolver os maiores pedaços possíveis do problema primeiro.

O método guloso funciona bem quando estamos usando moedas dos EUA, mas suponha que sua empresa decide implantar suas máquinas de venda automática na Elbonia do Sul onde, além das habituais moedas de 1, 5, 10 e 25 centavos dos EUA, também tem uma moeda de 21 centavos. Neste exemplo, o nosso método guloso não consegue encontrar a solução ideal para o troco de 63 centavos. Com a adição da moeda de 21 centavos o método guloso ainda encontra a solução com seis moedas. No entanto, a resposta ótima seria três moedas de 21 centavos.

Vamos ver um método onde podemos ter certeza de que encontraríamos a resposta ótima para o problema. Como esta seção é sobre recursão, você pode ter adivinhado que usaremos uma solução recursiva. Vamos começar com a identificação do caso base. Se estamos tentando fazer troco para a mesma quantia que o valor de uma das nossas moedas, a resposta é simplesmente uma dessas moedas.

Se o valor não corresponder, temos várias opções. O que nós queremos é o mínimo de 1 centavo mais o número de moedas necessárias para fazer o troco para o valor original menos 1 centavo, ou o mínimo de 5 centavos mais o número de moedas necessárias para fazer o troco para o valor original menos 5 centavos, ou 10 centavos mais o número de moedas necessárias para fazer o troco para o valor original menos dez centavos, e assim por diante. Então o número de moedas necessárias para fazer o troco para o valor original pode ser calculado de acordo com o seguinte:

O algoritmo para fazer o que acabamos de descrever é mostrado na Listagem 7. Na linha 3, estamos verificando nosso caso base; isto é, estamos tentando fazer o troco exato usando apenas uma de nossas moedas. Se não tivermos uma moeda igual ao troco necessário, fazemos chamadas recursivas usando cada moeda menor do que a quantidade de troco que estamos tentando fazer. A linha 6 mostra como filtramos a lista de moedas para aquelas com valor menor que o troco usando list comprehension. A chamada recursiva também reduz a quantidade total de troco que precisamos fazer pelo valor da moeda selecionada. A chamada recursiva é feita na linha 7. Observe que nessa mesma linha nós adicionamos 1 ao número de moedas para contabilizar o seu uso no troco. Adicionar 1 diretamente economiza uma chamada recursiva pedindo para fazer o troco no valor da moeda, que cairia imediatamente em um caso base.

Listagem 7

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def recMC(coinValueList,change):
   minCoins = change
   if change in coinValueList:
     return 1
   else:
      for i in [c for c in coinValueList if c <= change]:
         numCoins = 1 + recMC(coinValueList,change-i)
         if numCoins < minCoins:
            minCoins = numCoins
   return minCoins

print(recMC([1,5,10,25],63))

O problema com o algoritmo na Listagem 7 é que ele é extremamente ineficiente. De fato, são necessárias 67.716.925 chamadas recursivas para encontrar a solução ótima para o problema de fazer o troco de 63 centavos com 4 moedas! Para entender a falha fatal em nossa abordagem observe a Figura 3, que ilustra uma pequena fração das 377 chamadas de função necessárias para encontrar o conjunto ótimo de moedas para fazer o troco de 26 centavos.

Cada nó no grafo corresponde a uma chamada para recMC. O rótulo em um nó indica a quantidade de troco para a qual estamos computando o número de moedas. O rótulo de uma seta indica a moeda que acabamos de usar. Seguindo o grafo podemos ver a combinação de moedas que nos levou a qualquer ponto do grafo. O principal problema é que estamos refazendo cálculos demais. Por exemplo, o grafo mostra que o algoritmo iria recalcular o número ótimo de moedas para fazer o troco de 15 centavos pelo menos três vezes. Cada uma dessas computações para encontrar o número ótimo de moedas para fazer 15 centavos de troco, usa 52 chamadas de função. Claramente estamos perdendo muito tempo e esforço recalculando resultados.

Figura 3: Árvore de Chamadas para a Listagem 7¶

A chave para reduzir a quantidade de trabalho que fazemos é lembrar de alguns dos resultados anteriores para que possamos evitar recalcular resultados que já conhecemos. Uma solução simples é armazenar os resultados do número mínimo de moedas em uma tabela assim que são calculados. Então antes de calcularmos um novo mínimo, primeiro verificamos a tabela para ver se um resultado já é conhecido. Se já houver um resultado na tabela, usamos o valor da tabela em vez de recalcular. O ActiveCode 1 mostra uma modificação do algoritmo para incorporar nossa solução com tabela.

Observe que na linha 6 nós adicionamos um teste para ver se a nossa tabela contém o número mínimo de moedas para uma determinada quantia de troco. E se ela não contém, calculamos o mínimo recursivamente e o armazenamos na tabela. Usando este algoritmo modificado, o número de chamadas recursivas que precisamos fazer para o problema de troco de 63 centavos usando 4 moedas se reduz para 221 chamadas!

Embora o algoritmo no AcitveCode 1 esteja correto, ele dá a impressão de ser um hack. Além disso, se olharmos para as listas knownResults (resultados conhecidos) podemos ver que existem alguns buracos na tabela. Na verdade, o termo para o que fizemos não é programação dinâmica, mas melhoramos o desempenho do nosso programa usando uma técnica conhecida como “memoização” (memoization), ou mais comumente chamado de “caching”.

Um algoritmo de programação verdadeiramente dinâmico tratará o problema de forma mais sistemática. Nossa solução de programação dinâmica vai começar fazendo troco para 1 centavo e sistematicamente gerar outros valores de troco até chegar na quantidade necessária. Isso nos garante que a cada passo do algoritmo já sabemos o número mínimo de moedas necessárias para fazer o troco para qualquer quantia menor.

Vejamos como preencher uma tabela com as quantidades mínimas de moedas para fazer o troco de 11 centavos. A Figura 4 ilustra o processo. Nós começamos com um centavo. A única solução possível é uma moeda de 1 centavo. A próxima linha mostra o mínimo para 1 e 2 centavos. Mais uma vez, a única solução para 2 centavos é usando 2 moedas de 1 centavo. A quinta fila é onde as coisas começam a ficar interessantes. Agora temos duas opções a considerar, 5 moedas de 1 centavo ou 1 moeda de 5 centavos. Como decidimos qual é a melhor? Começando pela moeda de 1 centavo, consultamos a tabela e vemos que o número de moedas necessárias para fazer troco para 4 centavos é 4, mais 1 centavo para totalizar 5, resultando em cinco moedas. Ou podemos usar zero moedas de 1 centavo e uma moeda 5 centavos, no total de 1 moeda. Como o mínimo entre 1 e 5 é 1, armazenamos 1 na tabela. Vamos já avançar para o final da tabela e considerar 11 centavos. A Figura 5 mostra as três opções que temos que considerar:

1. Uma moeda de 1 centavo mais o número mínimo de moedas para fazer troco para \(11-1 = 10\) centavos (1)

2. Uma moeda de 5 centavos mais o número mínimo de moedas para fazer troco para \(11 - 5 = 6\) centavos (2)

3. Uma moeda de 10 centavos mais o número mínimo de moedas para fazer troco para \(11 - 10 = 1\) centavo (1)

Tanto a opção 1 quanto a 3 nos dá um total de 2 moedas, que é o número mínimo de moedas para o troco de 11 centavos.

Figura 4: Mínimo Número de Moedas Necessárias para Fazer o Troco¶

Figura 5: Três Opções a Considerar para o Número Mínimo de Moedas para 11 Centavos¶

A Listagem 8 mostra um algoritmo de programação dinâmica para resolver nosso problema de troco. A função dpMakeChange (faz troco) aceita três parâmetros: uma lista de valores de moedas, a quantidade de troco que queremos fazer e uma lista com as quantidades mínimas de moedas necessárias para cada valor. Quando a função termina, minCoins irá conter a solução para todos os valores de 0 até o valor de change (troco).

Listagem 8

1
2
3
4
5
6
7
8

def dpMakeChange(coinValueList,change,minCoins):
   for cents in range(change+1):
      coinCount = cents
      for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents-j] + 1 < coinCount:
               coinCount = minCoins[cents-j]+1
      minCoins[cents] = coinCount
   return minCoins[change]

Note que dpMakeChange não é uma função recursiva, apesar de termos começado com uma solução recursiva para este problema. É importante perceber que só porque você pode escrever uma solução recursiva para um problema não significa que esta é a melhor solução ou a mais eficiente. Grande parte do trabalho nesta função é feito pelo loop que começa na linha 4. Neste loop, consideramos o uso de todas as moedas possíveis para fazer o troco para o valor especificado por cents. Como fizemos para o exemplo do troco de 11 centavos acima, guardamos o valor mínimo na lista minCoins.

Embora nosso algoritmo de troco consiga descobrir a quantidade mínima de moedas, isso não nos ajuda a fazer o troco uma vez que não sabemos que moedas foram usadas. Podemos facilmente estender a função dpMakeChange para manter as moedas usadas simplesmente guardando a última moeda que adicionamos para cada entrada na tabela minCoins. Se sabemos qual foi a última moeda adicionada, podemos subtrair o valor da moeda para encontrar uma entrada anterior na tabela que nos diz a última moeda adicionada que resulta no valor restante. Podemos continuar percorrendo a tabela até chegarmos ao início.

O ActiveCode 2 mostra o algoritmo dpMakeChange modificado para guardar as moedas usadas, juntamente com uma função printCoins que percorre a tabela para imprimir o valor de cada moeda utilizada. Isso mostra o algoritmo em ação resolvendo o problema para nossos amigos na Elbonia do Sul. As duas primeira linhas da função main definem o valor a ser convertido e criam a lista de moedas usadas. As duas próximas linhas criam as listas para armazenar os resultados. A lista coinsUsed (moedas usadas) armazena as moedas usadas para fazer o troco, e coinCount (conta moeda) guarda o número mínimo de moedas utilizadas para fazer o troco para o valor correspondente à posição na lista.

Observe que as moedas que são impressas vêm diretamente da lista “coinsUsed”. Para a primeira chamada, começamos na posição 63 e na impressão 21. Então pegamos \(63 - 21 = 42\) e olhamos o 42º elemento da lista. Mais uma vez encontramos um 21 armazenado lá. Finalmente, o elemento 21 da lista também contém 21, resultando em três moedas de 21 centavos.