Técnicas de Síntese de Algoritmos

Nesta cadeira são estudadas três principais técnicas para síntese de algoritmos:

• Dividir para Conquistar, abordada na secção anterior.
• Programação Dinâmica, já abordada de relance na secção introdutória, aprofundada aqui.
• Algoritmos Greedy, abordada pela primeira vez aqui.

Programação Dinâmica

Vamos, então, aprofundar o tema da programação dinâmica.

Pode ser útil rever o exemplo da sequência de Fibonacci na secção introdutória destes resumos.

O problema sobre o qual nos vamos debruçar mais é o Problema da Mochila/Knapsack Problem. Trata-se de um problema clássico de introdução ao tema da programação dinâmica, dado que tem várias abordagens mais óbvias - e definitivamente não-ótimas - que são úteis de dissecar para perceber porque é que estão mal, e por onde podemos ir para obter uma abordagem melhor. Resta realçar que, nesta subsecção, vamos apenas olhar para o problema da mochila não fracionária: não podemos colocar quantidades fracionárias de itens na mochila, ou se coloca o item todo ou não se coloca.

Problema da Mochila com Repetição

Vamos, primeiro, olhar para a versão do problema com repetição - o mesmo objeto pode ser adicionado à mochila mais do que uma vez - e para algumas estratégias que podiam, erradamente, ser escolhidas para o resolver.

Como podemos observar, não aparenta haver uma escolha ótima - não parece dar para afirmar "aquele objeto tem definitivamente de estar na mochila". Temos, portanto, de olhar para todas as opções.

Procuramos, em programação dinâmica, definir a quantidade que queremos recursivamente. Neste caso, será dado por $v[i, j]$, o valor máximo que é possível transportar se o peso limite é $j$, com $j \leq W$, e se apenas podem ser selecionados os objetos numerados de $1$ a $i$. A solução ótima encontra-se em $v[n, W]$.

Corresponde a algo como:

#define max(a, b) (a > b ? a : b)

int knapsack(
  std::vector<int> values,
  std::vector<int> weights,
  int maxWeight
) {
  if (maxWeight == 0) return 0;

  int maxValue = 0;
  int numObjects = weights.size();
  for (int i = 0; i < numObjects; i++) {
    if (weights[i] <= maxWeight) {
      maxValue = max(
        maxValue,
        knapsack(values, weights, maxWeight - weights[i]) + values[i]
      );
    }
  }

  return maxValue;
}

Esta é, contudo, uma solução péssima. Tendo $w$ como o peso máximo e $n$ como o número de objetos:

Ou seja, a complexidade temporal da função é $O(n^w)$. Consideramos $T(w - 1), T((w - 1) - 1), \text{ etc }$ porque, no pior caso, estamos sempre a retirar objetos com peso 1 (considerando apenas peso naturais), e daí podemos retirar a natureza exponencial do problema. A primeira chamada pode correr $n$ vezes, mas cada uma das seguintes também pode correr $n$ vezes, e assim sucessivamente, $w$ vezes.

Ora, mas o número de subproblemas distintos é $n \cdot W$ (corresponde ao número de entradas numa possível tabela de resolução do problema com DP). Assim sendo, podemos definitivamente obter uma solução mais eficiente para o problema, sem fazer os mesmos cálculos mais do que uma vez, coisa que acontece na implementação acima.

int knapsack(std::vector<int> values,
             std::vector<int> weights,
             int maxWeight) {
  int numElements = weights.size();
  // inicializar um vetor para substituir as chamadas recursivas
  // todos os indices sao inicializados a 0
  std::vector<int> k = std::vector<int>(maxWeight + 1, 0);
  for (int w = 1; w <= maxWeight; w++) {
    k[w] = k[w - 1]; // o valor guardado na mochila nunca
                     // é menor que o anterior
    for (int i = 0; i < numElements; i++) {
      if (weights[i] <= w) {
        k[w] = std::max(
          k[w],
          k[w - weights[i]] + values[i]
        );
      }
    }
  }

  return k[w];
}

É possível que ver o vídeo seguinte e seguir o algoritmo ajude:

Este algoritmo corre exatamente $n \cdot W$ vezes - $\Theta (n \cdot W)$ - já que não temos nenhum break a meio do loops nem nenhuma chamada recursiva a meio. É, portanto, uma abordagem muito melhor do que a exponencial anterior.

Problema da Mochila sem Repetição

O problema da mochila sem repetição permite-nos olhar para o problema de uma maneira diferente - aqui, vamos, na recursão, procurar o valor máximo que se consegue transportar na mochila até a um certo índice $i$ - no problema com repetição não podíamos fazê-lo, dado que um mesmo objeto podia ser contado duas vezes. Podemos, então, definir a quantidade recursiva como

O segundo ramo corresponde a "vou ou não usar o elemento de índice $i$"?

Em código, corresponderia a algo deste género:

#define max(a, b) (a > b ? a : b)

int knapsack(
  std::vector<int> values,
  std::vector<int> weights,
  int maxWeight
) {
  int numElements = weights.size();
  std::vector<int> prevColumn = std::vector<int>(maxWeight + 1, 0);
  std::vector<int> currColumn = std::vector<int>(maxWeight + 1, 0);

  for (int i = 0; i < numElements; i++) {
    for (int w = 1; w <= maxWeight; w++) {
      if (weights[i] <= w) {
        currColumn[w] = currColumn[w - 1];
        currColumn[w] = max(
          prevColumn[w],
          prevColumn[w - weights[i]] + values[i]
        );
      }
    }
    prevColumn = currColumn;
  }

  return currColumn.back();
}

Aqui, o algoritmo volta a ser $\Theta(n \cdot W)$.

Este problema podia, claro, ser resolvido recorrendo à memoization, caso optássemos por passar a tabela como argumento da função e a fôssemos preenchendo. O trade-off seria que a memoization, apesar de só calcular o que realmente é necessário (que, no pior caso, é tudo), ocupa mais espaço $(\Theta(W) \text{ vs } \Theta(n))$.

Maior Subsequência Comum (LCS)

Não podemos, obviamente, verificar literalmente todas as subsequências possíveis - cada sequência tem $2^{\text{length}}$ subsequências, tornando-se impraticável fazer a comparação. Podemos, contudo, procurar tirar algumas conclusões sobre o problema:

• se duas sequências têm o último elemento igual, então esse elemento faz necessariamente

• parte da LCS, e procuramos os próximos elementos que fazem parte da LCS "cortando" o último elemento de cada sequência;

• caso o último elemento não seja igual, então das duas uma:

  • procuramos a maior subsequência comum "cortando" o último elemento da primeira subsequência;

  • procuramos a maior subsequência comum "cortando" o último elemento da segunda subsequência.

Em ambos os casos, voltamos a repetir estes passos sucessivamente, até chegar ao caso base (onde já não podemos cortar mais elementos).

Podemos definir esta recursão tal que, tendo duas sequências $X$ e $Y$:

Onde aqui $i$ e $j$ correspondem, respetivamente, a índices de elementos de $X$ e $Y$.

Utilizando programação dinâmica, podemos implementar um algoritmo que resolve este problema em $\Theta(nm)$, onde $n$ e $m$ são os comprimentos de cada sequência:

#define max(a, b) (a > b ? a : b)

int lcs(std::string x, std::string y) {
  std::vector<std::vector<int>> lengths =
    std::vector<std::vector<int>>(
      x.size() + 1,
      std::vector<int>(y.size() + 1, 0)
    );
  int lenX = x.size();
  int lenY = y.size();

  for (int i = 0; i <= lenX; i++) {
    for (int j = 0; j <= lenY; j++) {
      if (i == 0 || j == 0) {
        lengths[i][j] = 0;
      } else if (x[i - 1] == y[j - 1]) {
        lengths[i][j] = lengths[i - 1][j - 1] + 1;
      } else {
        lengths[i][j] = max(lengths[i - 1][j], lengths[i][j - 1]);
      }
    }
  }

  return lengths[lenX][lenY];
}

Podemos observar a matriz resultante de resolver o problema da LCS das sequências "BDCABA" e "ABCBDAB":

Aqui, não podemos escolher preencher a matriz só recorrendo à última coluna (como no último problema que tínhamos visto), pelo que a complexidade especial passa, necessariamente, por $\Theta(nm)$. Olhando para cada entrada da matriz, podemos ainda observar que o algoritmo é respeitado - caso estejamos na presença de 2 letras iguais, a entrada cresce em 1 sem depender dos elementos à sua esquerda/acima dela; caso contrário, está diretamente dependente do máximo entre esses dois elementos.

Multiplicação de Cadeias de Matrizes

O problema colocado é, dado um número arbitrário de matrizes (por uma certa ordem), descobrir a maneira mais eficiente (menor número de operações) para calcular o seu produto encadeado. Por exemplo, dadas três matrizes $A_1, A_2, A_3$, fazer o seu produto pela ordem $(A_1 \cdot A_2) \cdot A_3$ é diferente de fazer o produto pela ordem $A_1 \cdot (A_2 \cdot A_3)$ - consoante a colocação dos parêntesis, o custo muda.

No caso exposto acima, o custo varia entre:

• $(n_0 \cdot n_1 \cdot n_2) + n_0 \cdot n_2 \cdot n_3$

• $(n_1 \cdot n_2 \cdot n_3) + n_0 \cdot n_1 \cdot n_3$

Temos, tendo duas matrizes $A_1$, $n_0 \times n_1$, e $A_2$, $n_1 \times n_2$, que o número de operações necessárias para fazer o seu produto é $n_0 \cdot n_1 \cdot n_2$:

O número de colocação de parêntesis cresce exponencialmente com o número de matrizes, pelo que, mais uma vez, não será célere experimentar todas as opções. Devemos, portanto, definir a recursão do problema, e procurar resolvê-lo utilizando programação dinâmica.

Tenhamos que $c(i, j)$ corresponde ao número mínimo de operações (produtos escalares) necessários para calcular os produtos das matrizes $A_i$ à $A_j$:

Este segundo ramo equivalente a encontrar a colocação de parêntesis ótima para que um produto

tenha o menor custo operacional associado possível.

A solução proposta (utilizando DP) tem complexidade temporal $\Theta(O(n^3))$, podendo, contudo, ser melhorada para uma solução quadrática.

Algoritmos Greedy

Estão, de seguida, alguns problemas cuja resolução pode ajudar a perceber a abordagem greedy.

Problema da Mochila Fracionária sem Repetição

Voltamos, aqui, ao problema da mochila sem repetição, com um twist - desta vez, podemos colocar quantidades fracionárias de itens na mochila. Isto é, podemos colocar, por exemplo, meio objeto na mochila - coisa que não podia acontecer nas variantes do problema apresentadas acima.

Tenhamos, por exemplo, uma mochila que pode levar até 50kg, e três objetos:

• um primeiro objeto que pesa 10kg e vale 60€;
• um segundo objeto que pesa 20kg e vale 100€;
• um terceiro objeto que pesa 30kg e vale 120€;

Será que podemos encontrar uma escolha greedy aqui? Bem, neste caso, como podemos "dividir" objetos, existe uma escolha ótima a cada passo - colocar os itens na mochila por ordem decrescente de densidade (€/kg). Tentamos sempre colocar o objeto inteiro. Quando não pudermos, o algoritmo para - colocamos a fração que podemos, e a partir daí a mochila está no seu limite de peso.

Temos que a densidade de cada um dos objetos acima é, respetivamente, 6€/kg, 5€/kg e 4€/kg. Agora, teríamos de os ordenar por ordem decrescente de densidade (fantástico, já estão), e passar à fase "relevante" do algoritmo: colocá-los na mochila. Dar-se ia tal que:

• num primeiro momento, a mochila ainda pode levar mais 50kg, e o objeto com maior densidade só pesa 10kg, pelo que o podemos colocar todo. A mochila fica a valer 60€, e pode, agora, levar mais 40kg;

• num segundo momento, a mochila ainda pode levar mais 40kg, e o objeto com mais densidade (restante) só pesa 20kg, pelo que o podemos colocar todo. A mochila fica a valer 160€, e pode, agora, levar mais 20kg;

• num terceiro e último momento, a mochila ainda pode levar mais 20kg. Contudo, o próximo objeto pesa 30kg, pelo que não o podemos colocar todo - colocamos 2/3 da sua quantidade, e o respetivo valor também é cortado (são colocados 80€ do objeto 3). A mochila passa, assim a valer 240€, e a mochila está completamente cheia. Pelo que o algoritmo para.

O código para este algoritmo seria qualquer coisa como:

int fracKnapsack(
  std::vector<int> values,
  std::vector<int> weights,
  int maxWeight
) {
  // Assumimos, aqui, que os objetos estão ordenados
  // por ordem decrescente de densidade
  int maxValue = 0;
  for (uint i = 0; maxWeight != 0 && i < weights.size(); i++) {
    if (maxWeight >= weights[i]) {
      maxWeight -= weights[i];
      maxValue += values[i];
    } else {
      float ratio = (float) maxWeight / weights[i];
      maxValue += values[i] * ratio;
      maxWeight = 0;
    }
  }
  return maxValue;
}

A complexidade é linear, $O(n)$ (de realçar que, sem a condição de paragem maxWeight == 0 seria $\Theta(n)$, dado que correria sempre as $n$ iterações).

Seleção de Atividades

O problema consiste em, tendo um conjunto de $n$ atividades que pretendem usar um recurso (e que não o podem usar ao mesmo tempo), encontrar o máximo de atividades mutuamente compatíveis - isto é, o máximo de atividades que conseguimos arranjar que não se "cruzam" com nenhuma das outras. Cada atividade é caraterizada pelo seu tempo de início e de fim. Iremos considerar que estão ordenadas por ordem crescente de tempo de fim.

Podemos aqui fazer, também, uma escolha greedy:

• Não é escolher, a cada momento, a atividade que começa mais cedo. Tendo, por exemplo, três atividades tais que:

  • $A_1$ começa à hora 1 e acaba à hora 4;

  • $A_2$ começa à hora 2 e acaba à hora 3;

  • $A_3$ começa à hora 3 e acaba à hora 4.

  Aqui, a suposta escolha ótima levaria a podermos ter apenas uma tarefa compatível, quando na verdade existem duas - temos, portanto, um contraexemplo que nos impossibilita de optar por esta escolha.

• Não é escolher, a cada momento, a que ocupa menos tempo. Tendo, por exemplo, três atividades tais que:

  • $A_1$ começa à hora 8 e acaba à hora 11;

  • $A_2$ começa à hora 1 e acaba à hora 9;

  • $A_3$ começa à hora 10 e acaba à hora 20.

  Mais uma vez, a escolha ótima levar-nos-ia a apenas uma tarefa compatível, quando na verdade existem duas - mais uma vez, um contraexemplo.

A escolha greedy é, aqui, optar sempre pela próxima atividade que acabar mais cedo.

Seguindo esta escolha greedy, conseguíamos construir um algoritmo para calcular o maior número de atividades mutuamente compatíveis semelhante ao abaixo:

int activitySelection(std::vector<int> start, std::vector<int> finish) {
  // Consideramos que as atividades estão ordenadas por tempo de fim
  int numElements = start.size();
  if (numElements == 0) return 0;

  int finishTime = finish[0];
  int count = 1;

  for (int i = 1; i < numElements; i++) {
    if (start[i] >= finishTime) {
      count++;
      finishTime = finish[i];
    }
  }

  return count;
}

O algoritmo acima apresenta complexidade temporal $O(n)$ e espacial $O(1)$.

Algoritmo de Huffman

O algoritmo de Huffman tem como objetivo a construção de códigos binários ótimos. Consiste em "comprimir os dados", reduzindo o seu tamanho, sem perder detalhes sobre os mesmos. É bastante útil para comprimir dados com caracteres que ocorrem frequentemente.

Podemos representar códigos livres de prefixo através de árvores binárias - é, aliás, nelas que o algoritmo de Huffman assenta.

O conjunto de caracteres, com código binário tal que

é livre de prefixo, já que nenhum código é prefixo de outro. Podemos representar o código com uma árvore binária (de realçar que aqui optamos por o 0 ser à esquerda e o 1 à direita, mas depende da implementação do algoritmo - no enunciado dos exercícios que eventualmente saírem vem especificado o sentido a escolher):

Se seguirmos o "caminho" da árvore binária, podemos observar o código a ser construído.

Temos, portanto, que o algoritmo de Huffman quererá minimizar o custo do código binário. O produto de um caracter muito frequente deve, num modelo ótimo, ser realizado com uma profundidade menor.

O algoritmo em si passa por, inicialmente, considerar todos os caracteres como nós, com valor igual à frequência. Cria-se uma min priority queue (com prioridade igual ao valor), e inserem-se os nós na mesma. De seguida, extraem-se os dois nós com valor menor e somam-se os respetivos valores, criando um novo nó com valor igual a essa soma. Este nó é inserido na queue, e assim sucessivamente $|\Sigma| - 1$ vezes, onde $|\Sigma|$ corresponde ao tamanho do alfabeto. O pseudocódigo é o seguinte:

Huffman(alphabet)
  let Q be a min priority queue with the elements of alphabet
  for i := 1 to |alphabet| - 1
    let x := extract_min(Q) // complexidade é O(log |alphabet|)
    let y := extract_min(Q) // complexidade é O(log |alphabet|)
    let z := newNode()
    z.freq = x.freq + y.freq
    z.left = x
    z.right = y
    insert(z, Q) // complexidade desta operação é O(log |alphabet|)

O algoritmo está, claro, inserido na categoria dos algoritmos Greedy: tem, portanto, uma escolha greedy associada. Aqui, a escolha consiste em extrair sempre os dois nós com menor frequência associada, procurando criar um nó com valor igual a soma dos valores dos dois nós.

• Notas da Aula 4 - Prof. José Fragoso

• Notas da Aula 5 - Prof. José Fragoso

• Notas da Aula 6 - Prof. José Fragoso