Análise de Algoritmos | Aulas | Dicionário | Índice

Método Guloso

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.

— Ian Parberry, Problems on Algorithms

Esta página é uma introdução à estratégia gulosa (= greedy strategy) de solução de problemas computacionais. Poderíamos apresentar o assunto como paradigma guloso de concepção de algoritmos, ou como método guloso de projeto de algoritmos.

Estratégia gulosa é aquela usada por um montanhista que decide caminhar sempre para cima, na direção de maior subida, na esperança de assim chegar ao pico mais alto da montanha. (Como todos sabemos, essa estratégia nem sempre produz o resultado esperado.)

Um algoritmo guloso escolhe, em cada iteração, o objeto mais apetitoso que vê pela frente. (A definição de apetitoso é estabelecida a priori, antes da execução do algoritmo.) 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 naturalmente corretos, a prova de sua correção é, em geral, difícil e sutil. Para compensar, algoritmos gulosos são muito eficientes. Mas os problemas que admitem solução gulosa são um tanto raros.

Veja o capítulo 16 do livro CLRS.

O problema do pendrive

Tenho n arquivos digitais no meu computador. Cada arquivo i tem t_i megabytes. Quero gravar o maior número possível de arquivos num pendrive que tem capacidade para c megabytes. O problema pode ser formulado assim: encontrar o maior subconjunto X do intervalo 1 .. n que satisfaça a restrição

(Note que queremos maximizar ⎮X⎮ e não a soma ∑_i ∈ X t_i.)

O seguinte algoritmo de caráter guloso resolve o problema. Em cada iteração, se a capacidade do pendrive não estiver esgotada, o algoritmo escolhe o menor dos arquivos que ainda não foram gravados. O algoritmo é guloso pois abocanha o menor arquivo sem antes pesar os prós e contras dessa escolha. Embora a estratégia pareça natural, não é óbvio que ela produz o resultado desejado.

Se os arquivos são dados em ordem crescente de tamanho, ou seja, se t₁ ≤ t₂ ≤  …  ≤ t_n, é muito fácil descrever o algoritmo em código:

Embora a lógica do algoritmo pareça muito natural, não é óbvio que ela leva à solução do problema. A prova da correção do algoritmo é dificultada pela fato de que cada instância do problema pode ter muitas soluções.

A correção do algoritmo Pendrive decorre da seguinte observação: toda instância do problema do pendrive tem uma solução X que é um segmento inicial do intervalo 1 .. n, ou seja,

para algum k ≤ n. Para provar essa proposição usaremos um conceito auxiliar: diremos que o topo de um conjunto X é o maior elemento de X. Agora escolha uma solução X do problema que tenha o menor topo possível. Seja k esse topo. Mostraremos a seguir que X = { 1, … , k }.

Suponha por um momento que X ≠ { 1, … , k } e seja h um número em { 1, … , k } − X. Como t_h ≤ t_k, temos (∑_i ∈ X t_i) − t_k + t_h ≤ ∑_i ∈ X t_i. Logo, o conjunto (X − { k }) ∪ { h } satisfaz a restrição (A) e tem o mesmo tamanho que X, sendo portanto uma solução do problema. Como o topo do novo conjunto é menor que o topo de X, temos uma contradição. A contradição mostra que X = { 1, … , k }. Portanto, a proposição (B) está correta, CQD.

Exemplos de algoritmo gulosos

Eis uma pequena lista de problemas que admitem soluções gulosas (ou seja, podem ser resolvidos por algoritmos gulosos):

• intervalos disjuntos,
• mochila fracionária,
• árvore de Huffman,
• caminho de peso mínimo,
• árvore geradora de peso mínimo num grafo,
• 2-aproximação de cobertura mínima de um grafo.

Gula versus programação dinâmica

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

À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

• abocanha a alternativa mais promissora (sem explorar as outras),
• é muito rápido,
• nunca se arrepende de uma decisão já tomada,
• não tem prova de correção simples.

Um algoritmo de programação dinâmica

• explora todas as alternativa (mas faz isso de maneira eficiente),
• é um tanto lento,
• a cada iteração pode se arrepender de decisões tomadas anteriormente (ou seja, pode rever o ótimo corrente),
• tem prova de correção simples.