Esta página é uma introdução à estratégia gulosa (= gananciosa = greedy) de solução de problemas. Poderíamos também apresentar o assunto como paradigma guloso na concepção de algoritmos.
Para resolver um problema, um algoritmo guloso escolhe, em cada iteração, o objeto mais "apetitoso" que vê pela frente. (A definição de "apetitoso" é establecida a priori.) O objeto escolhido passa a fazer parte da solução que o algoritmo constrói.
Um algoritmo guloso é "míope": ele toma decisões com base nas informações disponíveis na iteração corrente, sem olhar as consequências que essas decisões terão no futuro. Um algoritmo guloso jamais se arrepende ou volta atrás: as escolhas que faz em cada iteração são definitivas.
Embora algoritmos gulosos pareçam óbviamente corretos, a prova de sua correção é, em geral, muito sutil. Para compensar, algoritmos gulosos são muito rápidos e eficientes. (É preciso dizer, entretanto, que os problemas que admitem soluções gulosas são um tanto raros.)
Veja o capítulo 16 do CLRS. Veja também o verbete Greedy algorithm na Wikipedia.
Suponha que S é uma coleção de subconjuntos de {1,…,n}. Um elemento X de S é máximo se não existe Y em S tal que |Y| > |X| , ou seja, se nenhum elemento de S é maior que X. Um elemento X de S é maximal se não existe Y em S tal que Y ⊃ X , ou seja, se nenhum elemento de S é superconjunto próprio de X. É evidente que todo máximo é maximal. Mas a recíproca longe está de ser verdadeira.
Exemplo: Sejam {1,2}, {2,3}, {4,5}, {1,2,3}, {1,2,4}, {2,3,4,5} e {1,3,4,5} os elementos da coleção S. Então S tem dois elementos máximos: {2,3,4,5} e {1,3,4,5}. Há quatro elementos maximais: {1,2,3}, {1,2,4}, {2,3,4,5} e {1,3,4,5}.
Procurar por um elemento máximo de S é, em geral, uma tarefa computacionalmente pesada (pois exige que todos os elementos de S sejam examinados). Já encontrar um elemento maximal de S é muito fácil. Basta aplicar o seguinte algoritmo guloso, que abocanha o primeiro Y aceitável que vê pela frente:
| _ escolha algum X em S |
| _ enquanto X ⊂ Y para algum Y em S |
|
____
faça X ← Y |
| _ devolva X |
É ainda mais fácil encontrar um elemento maximal se a coleção S tiver caráter hereditário, ou seja, se tiver a seguinte propriedade: para cada X em S, todos os subconjuntos de X também estão em S. Nesse caso, basta executar o seguinte algoritmo guloso:
| _ X ← { } |
| _ para cada k em {1,…,n} faça |
| ____ Y ← X ∪ {k} |
| ____ se Y está em S |
| _______ então X ← Y |
| _ devolva X |
"A greedy algorithm starts with a solution to a very small subproblem and augments it successively to a solution for the big problem. The augmentation is done in a "greedy" fashion, that is, paying attention to short-term or local gain, without regard to whether it will lead to a good long-term or global solution. As in real life, greedy algorithms sometimes lead to the best solution, sometimes lead to pretty good solutions, and sometimes lead to lousy solutions. The trick is to determine when to be greedy.
[Most greedy algorithms are deceivingly simple.]
One thing you will notice about greedy algorithms is that they are
usually easy to design, easy to implement, easy to analyze,
and they are very fast,
but they are almost always difficult to prove correct."
— Ian Parberry, Problems on Algorithms
Um problema de otimização combinatória consiste em encontrar um elemento de valor ótimo num conjunto finito. Dependendo do problema, ótimo pode significar máximo ou mínimo. No caso da maximização, por exemplo, a estratégia de um algoritmo guloso é calcular um máximo "local" na esperança de encontrar um máximo "global". (É como um montanhista que anda sempre "para cima" na esperança de assim chegar ao pico mais alto da montanha.)
Suponha que n é um número grande e que S é uma enorme coleção de subconjuntos de {1,…,n}. (Nos casos concretos, a coleção S é dada de maneira indireta, e não como uma lista explícita de conjuntos.) Queremos encontar um elemento máximo de S. Se todos os elementos maximais de S têm o mesmo tamanho, então o problema admite solução gulosa, pois basta encontrar um elemento maximal.
Mesmo que nem todo maximal seja máximo, entretanto, um algoritmo de caráter guloso pode, às vezes, ter sucesso. Para certas coleções S, o algoritmo guloso abaixo produz um conjunto máximo se o universo {1,…,n} for examinado numa certa ordem "mágica":
| _ X ← { } |
| _ para cada k em {1,…,n} na ordem "mágica" faça |
| ____ Y ← X ∪ {k} |
| ____ se Y está em S |
|
_______
então X ← Y |
| _ devolva X |
Suponhamos, por exemplo, que a ordem "mágica" para um determinado S é a ordem decrescente. Para mostrar que o algoritmo produz um elemento máximo de S é preciso verificar que
No CLRS, a propriedade 1 é denominada Propriedade da Escolha Gulosa e a propriedade 2 é denominada Propriedade da Subestrutura Ótima.
Eis uma pequena lista de problemas admitem soluções gulosas (ou seja, podem ser resolvidos por algoritmos gulosos):
Problema: Programar as tarefas (ou seja, estabelecer uma bijeção entre as tarefas e os dias de trabalho) de modo a minimizar a multa total.
Escreva um algoritmo guloso para resolver o problema. Prove que seu algoritmo está correto. Analise o consumo de tempo.
Às vezes é difícil distinguir um algoritmo guloso de um algoritmo de programação dinâmica. A seguinte lista grosseira de características pode ajudar. Um algoritmo guloso
Um algoritmo de programação dinâmica