Introdução a algoritmos greedy

Embora seja conhecido como "algoritmos greedy", este tópico não se refere a um algoritmo em particular mas a um conceito algorítmico. A ideia parece muito simples: fazer a melhor escolha local com a esperança que isso leve a uma boa escolha global. Vamos ver o que isto significa e quando é que funciona.

Introdução

Para começar considerem o seguinte problema: são nos dados $N$ conjuntos de um universo de elementos $U$, ou seja, dado um conjunto de elementos $U$ (por exemplo, os número de 1 a $M$) e $N$ subconjuntos desse conjunto $S_1 \subseteq U, S_2 \subseteq U, \ldots, S_N \subseteq U$, queremos escolher alguns dos conjuntos de forma a que a união de todos os conjuntos seja $U$. Um exemplo deste problema seria: temos como universo $U = \{1, 2, 3, 4, 5\}$ e temos $N = 4$ conjuntos $S_1 = \{1, 2, 4\}, S_2 = \{1, 4\}, S_3 = \{5\}, S_4 = \{3, 4\}$. Se escolhermos todos os conjuntos temos que a sua união $S_1 \cup S_2 \cup S_3 \cup S_4 = U$, isto é, escolher todos os conjuntos é uma solução possível e é óbvio que se existe uma solução, então escolher todos os conjuntos é uma solução. Mas vamos complicar um pouco agora: qual o menor número de conjuntos que podemos escolher de modo a que a sua união seja o universo $U$? No exemplo anterior, podemos escolher apenas 3: $S_1, S_3$ e $S_4$ e é fácil de ver que não existe nenhuma solução melhor.

De volta aos algoritmos greedy e à ideia de local e global, como é que isto nos pode ajudar neste problema? Uma ideia simples e óbvia é fazer o seguinte: escolher o conjunto com maior número de elementos que não se encontram em nenhum dos conjuntos escolhidos anteriormente. Para o exemplo anterior, começamos por escolher $S_1$ pois tem 3 elementos não escolhidos, de seguida tanto $S_3$ como $S_4$ têm um elemento não escolhido, por isso vamos escolher o $S_3$ e finalmente escolhemos o $S_4$ e obtemos a resposta. Reparem que de cada vez fizemos uma escolha local: o conjunto que nos coloca o mais próximo do objetivo possível, ou seja, que cobre o maior número de novos elementos. Estamos a fazer a escolha que parece levar ao melhor resultado local, com a esperança que corresponda ao melhor resultado global. A algoritmos que sigam esta ideia chamamos de algoritmos greedy.

Infelizmente isto nem sempre funciona. Observem o seguinte exemplo do problema anterior: $U = \{1, 2, 3, 4, 5, 6\}$ e $N = 5$ com $S_1 = \{1, 2, 3\}$, $S_2 = \{4, 5, 6\}$, $S_3 = \{2, 3, 4, 5\}$, $S_4 = \{1\}$, $S_5 = \{6\}$. O nosso algoritmo greedy anterior vai escolher o conjunto $S_3$ inicialmente e depois vai escolher mais dois conjuntos, obtendo 3 como resposta. Mas podemos usar apenas os conjuntos $S_1$ e $S_2$ para obter o universo. Isto significa que o nosso algoritmo greedy não funciona. Na verdade, não se conhece nenhum algoritmo de complexidade polinomial, ou seja, da forma $O(N^c)$ para uma constante $c$ qualquer, que resolva este problema, por isso não percam muito a pensar como o resolver.

Um exemplo que realmente funciona

Mas afinal se um algoritmo greedy não resolve este prolema corretamente, será que há algum problema que resolva? Vamos ver um exemplo muito simples:

Neste problema, resumidamente, pedem-nos para calcular o número mínimo de saltos de comprimento máximo $d$ para chegar do ponto 1 ao ponto $n$, usando apenas os pontos indicados. Não é difícil de chegar à solução deste problema: o melhor a fazer é sempre saltar para o ponto de maior valor a que conseguimos chegar. Neste caso reparem como a escolha local (escolher o ponto de maior valor a que conseguimos chegar da posição em que estamos) leva à melhor solução global possível.

Verificar uma solução

Vamos voltar a pegar no exemplo do problema anterior, sobre calcular o número mínimo de saltos. O problema é tão simples que não precisavamos de saber nada sobre escolhas locais ou globais para o resolver, parece óbvio o melhor a fazer. Ainda assim, vamos usar este problema muito simples como um exercício: vamos tentar provar que esta solução realmente funciona. Intuitivamente é fácil de ver que esta solução está correta, mas vamos provar formalmente/matematicamente que realmente está correta.

Ora vamos usar uma técnica de prova conhecida por redução ao absurdo, ou seja, vamos assumir que a solução não funciona (ou seja, que existem instâncias em que a solução não chega ao mínimo número de saltos) e vamos mostrar que isto leva a um absurdo, ou seja, a algo impossível. Se assim for, podemos concluir que o que assumimos inicialmente está incorreto, ou seja, que a nossa solução está correta.

Vamos então assumir que a solução não funciona. Nesse caso existe uma instância qualquer (um input) qualquer, em que a solução chega a um número de saltos $s$ quando o número ótimo é $s^\star$ e $s^\star < s$. Seja $J$ a sequência de saltos que a solução devolve, ou seja $J$ contém $s$ saltos válidos (de comprimento máximo $d$), de $1$ para uma posição $J_1$, de $J_1$ para uma posição $J_2$, ..., de $J_{s - 1}$ para $n$. Seja $J^\star$ a sequência de saltos ótima, ou seja $J^\star$ contém $s^\star$ saltos válidos (de comprimento máximo $d$), de $1$ para uma posição $J_1$, ..., de $J_{s^\star - 1}$ para $n$.

Seja $i$ a primeira posição em $J^\star$ que difere da posição correspondente em $J$, ou seja, a primeira posição em que a solução decide saltar para uma posição diferente da ótima. Visto que a solução escolhe sempre o ponto de maior posição, temos que $J_i > J^\star_i$, pois visto que $J_{i - 1} = J^\star_{i - 1}$ (porque definimos que $i$ é a primeira posição em que diferem, em todas as posições anteriores são iguais) a solução pode chegar a $J^\star_i$. Mas então podemos construir uma nova sequência ótima da seguinte forma: usamos os primeiros $i - 1$ saltos de $J^\star$ (que, como vimos, são iguais aos primeiros $i$ saltos de $J$); de seguida saltamos para $J_i$; finalmente usamos os últimos $n - i - 1$ saltos de $J^\star$. Notem que esta sequência é válida, pois como $J_i > J^\star_i$, podemos saltar para qualquer posição à direita de $J^\star_i$ a partir de $J_i$. Notem ainda que esta sequência tem o mesmo número de saltos que $J^\star$, pois só substituimos o salto $i$ por $J_i$.

Vamos chamar a esta nova sequência ótima de $J^{\star\star}$. Reparem que podemos usar o mesmo argumento que fizemos no parágrafo anterior, mas com a posição $i'$, ou seja, a primeira posição em $J^{\star\star}$ que difere da posição correspondente em $J$. Temos ainda que $i' > i$, pois construimos $J^{\star\star}$ de forma a que os primeiros $i$ saltos são iguais aos correspondentes em $J$. Com isto podemos construir $J^{\star\star\star}$ de forma semelhante. E a partir de $J^{\star\star\star}$ contruimos $J^{\star\star\star\star}$ e por ai fora.

Visto que a cada construção temos que $i < i' < i'' < \ldots$ eventualmente chegaremos a uma sequência ótima cujos $s^\star$ primeiros saltos são iguais aos $s^\star$ primeiros saltos de $J$. Mas isto significa que $J$ é uma sequência ótima, ou seja, temos uma contradição ao que assumimos inicialmente. Concluimos assim que a solução está correta.

Porquê tanto formalismo?

A prova de correção anterior é bastante detalhada e formal, mas para quê perder tanto tempo a provar algo tão simples? Num concurso não precisamos de provar que a nossa solução está correta, mas é importante termos a certeza que assim o é. Dito isto, quando não temos a certeza da correção de uma solução um pouco mais difícil convém tentarmos convencer-nos e uma forma de o fazer é tentar provar a sua correção.

Ainda que o exemplo anteior seja muito simples, é comum que as provas de correção de um algoritmo greedy sigam a mesma estrutura, ou seja:

1. Assumir que a solução greedy está incorreta;
2. Considerar uma instância ótima que difere da solução greedy;
3. Mostrar que é possível modificar a instância ótima de forma a ficar mais próxima da solução greedy;
4. Repetir até construir uma instância ótima que obedece à propriedade local/greedy;

Tentem reler a prova anterior tendo isto em conta e observem o quão simples é, apesar de estar muito detalhada. Para mais informações sobre técnicas de prova de correção de algoritmos greedy consultem o artigo seguinte:

Aplicações

Antes de terminarmos este artigo introdutório, vamos tentar resolver alguns problemas. Vamos começar com um problema um pouco mais complicado que o anterior.

Notem que saber que a solução é greedy ajuda bastante para resolver o problema. Regra geral, a parte mais difícil de resolver um problema que admite uma solução greedy é convencer-nos que uma solução greedy é possível.

Se precisarem de uma dica observem o seguinte: calculem a melhor maneira de modificar a string de modo a terem $k$ dígitos 0, a melhor maneira de modificar a string de modo a terem $k$ dígitos 1, etc, e no fim escolham a melhor.

Mais um problema simples, com um estilo parecido ao anterior (desta vez sem dicas):

Após chegarem à solução, tentem provar, informalmente, que solução deste problema está correta usando o método anterior.

Finalmente, se quiserem, opcionalmente, tentar resolver um problema mais complicado, eis um bom exemplo:

* Provas mais avançadas

Provar a correção de algoritmos é importante em ciência de computadores, ainda que não seja absolutamente necessário em concursos. Se estiverem interessados em exemplos mais complexos e na teoria mais geral de algoritmos greedy o artigo seguinte é um bom começo:

Nota: este artigo requer alguma maturidade matemática e não é muito relevante para concursos, é apenas uma curiosidade teórica de ciência de computadores.