Algoritmos Gulosos

A special thanks to the TA Filipe Vilas Boas for scribing this page

Projeto de algoritmos usando estratégias gulosas¶

Estratégias gulosas para projeto de algoritmos são úteis em diversas áreas de estudo, desde algoritmos exatos até algoritmos aproximativos e heurísticas. Um algoritmo guloso é caracterizado por uma sequência de escolhas gulosas feitas com o objetivo de construir iterativamente uma solução final para um problema. Tal solução final geralmente é representada como um conjunto de itens definidos de acordo com o problema em questão. Uma escolha para ser gulosa deve possuir as seguintes características:

1. Localmente ótima: dentre as opções de escolha em um dado momento, precisa decidir incluir na solução aquele item que demonstrar o melhor benefício imediato. Naturalmente, diversos critérios podem ser usados para essa avaliação, o que nos dá margem para produzir mais de uma escolha gulosa para um problema;
2. Factível: não deve violar nenhuma restrição do problema;
3. Irrevocável: uma vez tomada, a escolha gulosa nunca mais será desfeita.

Como escolhas do algoritmo não são desfeitas, algoritmos gulosos tendem a ser eficientes em tempo mas nem sempre levam à solução ótima global. Quando isso acontece, temos um procedimento que pode ser um algoritmo aproximativo ou apenas uma heurística gulosa.

Por hora vamos focar nos problemas para os quais existem algoritmos gulosos ótimos que os solucionam. Para um dado problema e algoritmo guloso, duas propriedades devem ser garantidas para que a otimalidade da estratégia seja garantida:

• Propriedade da escolha gulosa: existe sempre alguma solução ótima para qualquer instância do problema que contém a escolha gulosa do algoritmo.
• Propriedade da subestrutura ótima: um problema atende essa propriedade se o mesmo puder ser decomposto em subproblemas e a solução ótima para o problema original puder ser construída a partir de soluções ótimas desses subproblemas.

Essas duas propriedades se verificadas em conjunto, simplificam a tarefa de demonstrar que um algoritmo guloso é ótimo. De fato, a outra alternativa seria demonstrar de forma indutiva que alguma invariante do algoritmo se mantém e garante a resposta correta – abordagem mais genérica, porém geralmente mais desafiadora.

Estudo de caso: problema do troco¶

// change-greedy(v, n)
// v: vetor de valores das moedas (ordenado decrescente)
// n: valor a ser trocado
troco = []
for i = 1 to |v|
   while n >= v[i]
      troco.adiciona(v[i])   // adiciona moeda ao troco
      n = n - v[i]
return troco

Estudo de caso: problema do escalonamento de tarefas¶

Cada tarefa $i$ é representada por um início $s_i$ e um término $f_i$. O objetivo é escalonar um conjunto de tarefas que não se sobrepõem (são compatíveis).

// schedule-compatible(s, f)
// s: vetor de tempos de início
// f: vetor de tempos de término
// n: número de tarefas
a = [1, 2, ..., n] // índices das tarefas
ordene a por f[i] crescente
T = conjunto vazio
i = 1
while i <= n
   m = a[i]
   T = T U {m}
   i = i + 1
   while i <= n and s[a[i]] < f[m] // incompatível
      i = i + 1
return T

O algoritmo acima é ótimo e, para garantir isso, precisamos verificar as duas propriedades pertinentes: (1) escolha gulosa; e (2) subestrutura ótima. Via de regra, com essas duas propriedades o algoritmo será automaticamente válido por indução: (1) garante que é sempre seguro fazer a escolha gulosa e ainda assim encontrar alguma solução ótima, isto é, passo base; e (2) garante que é seguro fazer a escolha gulosa a todo passo, para todos os subproblemas que forem sobrando, isto é, passo indutivo.

Vamos verificar cada uma das propriedades a seguir:

Propriedade da escolha gulosa¶

Como o conjunto de itens que compõem uma solução são exatamente as tarefas escolhidas, vamos representar o problema de escalonamento como um conjunto de todas essas tarefas candidatas. Portanto, seja $P = \{1, · · · , n\}$ o problema de escalonar essas $n$ tarefas. Assim, quando o algoritmo realiza a escolha gulosa (a tarefa $m$ de menor término), o subproblema restante a se resolver é: $P' = \{i ∈ P \mid s_i ≥ f_m\}$, isto é, o restante de tarefas compatíveis com $m$. Com isso, acabamos de decompor o problema original em subproblemas a partir da escolha gulosa do algoritmo. Da mesma forma, uma solução para $P$ que faz a escolha gulosa pode ser indicada como $S_p = \{m\} ∪ S_{p'}$.

Essa decomposição inicial é fundamental pois, de acordo com a propriedade da escolha gulosa, deveríamos ser capazes de transformar qualquer solução genérica ótima $S'_p$ em uma solução de igual qualidade $S_p$ que necessariamente faça a escolha gulosa (não confundir $S_{p'}$ com $S'_p$). Quase sempre, o argumento para garantir essa transformação é incluir a escolha gulosa na solução genérica (uma troca) de maneira a garantir a manter a otimalidade da solução.

Para o caso do escalonamento de tarefas, queremos transformar $S'_p$ em $S_p$ . Para isso, seja $m$ a escolha gulosa e seja $j$ a tarefa de menor término em $S'_p$ . Pense sobre isso, $m$ termina primeiro em $P$ e $j$ termina primeiro em uma solução genérica de $P$, denotada como $S'_p$ :

1. Se $m = j$, a solução genérica já faz a escolha gulosa. Portanto, $S_p = S'_p$ .

2. Se $m \not = j$, só pode ser que $f_j ≥ f_m$. Dessa forma, qualquer tarefa que seja compatível com $j$ também será compatível com $m$. Assim, trocar $j$ por $m$ em $S'_p$ não altera a qualidade nem a viabilidade da solução. Portanto, $S_p = (S'_p \, \backslash \, \{ j\}) ∪ \{m\}$.

Veja que em ambos os casos, a qualidade da solução não mudou porque a cardinalidade dos conjuntos permaneceu a mesma. Além disso, em ambos os casos, garantimos que m pertence à solução ótima.

Propriedade da subestrutura ótima¶

Subestrutura ótima tem tudo a ver com como problemas são decompostos em subproblemas. No caso de algoritmos gulosos, sempre teremos apenas um subproblema restante. Já fizemos essa decomposição na seção anterior, considerando a escolha gulosa que agora é segura: $S_p = \{m\} ∪ S_{p'}$ . Isso nos diz, que solução para $P$ inclui a escolha gulosa mais alguma solução para o subproblema restante $P'$.

A subestrutura ótima trata da seguinte questão: a solução do subproblema $S_{p'}$ precisa ser ótima para que a solução do problema original $S_p$ também seja ótima? Se a resposta for sim, o problema atende a propriedade da subestrutura ótima. Caso contrário, não atende. Veja que no caso de atender, estamos implicitamente afirmando que soluções ótimas para problemas são compostas de soluções também ótimas de seus respectivos subproblemas.

Para o problema do escalonamento, isso é facilmente verificado por contradição. Suponha que $S_p$ seja uma solução ótima para $P$, mas que $S_{p'}$ não seja ótima para $P'$. Dessa forma, deve existir uma solução ótima para $P'$, denotada como $S'_{p'}$ . Segue dessa definição que $|S'_{p'} | > |S_{p'} |$. Com isso, poderíamos construír uma solução para $P$ de melhor qualidade:

$\quad S'_p = {m} ∪ S'_{p'}$ , de cardinalidade $|S'_p | = 1 + |S'_{p'} | > |S_p | = 1 + |S_{p'} |$.

Isso contradiz a premissa de que $S_p$ é ótima. Conclusão, $S_{p'}$ precisa ser ótima também. Juntando este resultado com o resultado da propriedade da escolha gulosa, concluímos que o algoritmo que faz a escolha gulosa da tarefa de menor término primeiro no problema do escalonamento é ótimo.

Estudo de caso: árvore geradora mínima¶

// prim(g)
// g: grafo com vértices e arestas
Q = conjunto de todos os vértices de g
T = conjunto vazio // árvore resultante
for v in Q
   key[v] = infinito
   parent[v] = nulo
key[raiz] = 0
while Q não está vazio
   u = vértice em Q com menor key[u]
   remova u de Q
   for v in vizinhos de u
      if v in Q and peso(u, v) < key[v]
         parent[v] = u
         key[v] = peso(u, v)
   if parent[u] != nulo
      T = T uniao {(parent[u], u)}
return T

Estudo de caso: compressão de documentos¶

Seja um documento formado por caracteres, nosso objetivo será encontrar uma forma de comprimí-lo de forma ótima. Por exemplo, seja o seguinte documento:

$\fbox{ escolha gulosa e subestrutura otima }$

Se ignorarmos os espaços apenas para facilitar o exemplo, percebemos que é muito comum que a distribuição das frequências de caracteres seja bem desbalanceada. Para o exemplo acima:

Olhando para essas frequências, fica evidente que se representarmos cada caractere usando a mesma quantidade de bits, espaço seria desperdiçado com os caracteres que acontecem raramente. Assim, definimos este problema de compressão como: dados um conjunto de caracteres que ocorrem em um documento e suas respectivas frequências, queremos encontrar uma codificação para cada caratere que minimize a quantidade de bits necessária para representar o documento inteiro. Por conveniência, vamos representar essas codificações através de uma árvore binária de prefixos. Considerando um outro exemplo:

Em uma codificação de tamanho fixo, como temos apenas 6 caracteres no documento, 3 bits seriam suficientes, já que $2^3 = 8 ≥ 6$:

!! Incluir figura ...

Veja que com essa representação, temos a oportunidade de encontrar outras codificações melhores: possivelmente as que utilizem menos bits para caracteres mais frequentes e mais bits para caracteres menos frequentes. O objetivo do problema é portanto encontrar uma árvore codificadora $T$ como esta que minimize:

$B(T) = \sum_{c \, ∈ \, C} freq(c) ∗ d_T (c)$, onde $freq$ representa a frequência dos caracteres e $d_T$ representa a profundidade do caractere na árvore, isto é, quantos bits são utilizados para representá-lo.

O algoritmo a seguir implementa a codificação de Huffman, que é uma estratégia gulosa ótima para o problema:

// huffman(c, f)
// c: vetor de caracteres
// f: vetor de frequências
// n: número de caracteres
construa uma fila de prioridade Q com itens c[i] e prioridades f[i]
for i = 1 to n - 1
   l = extrai-min(Q)
   r = extrai-min(Q)
   z = novo nó de árvore binária
   filho-esquerdo(z) = l
   filho-direito(z) = r
   f(z) = f(l) + f(r)
   insira(Q, z, f(z))
return extrai-min(Q)