Os greedy algorithms

Quando estive revisando a disciplina de algoritmos, me deparei com os tais "algoritmos gulosos", ou greedy algorithms. Lembro que na época eu automaticamente associei o termo a soluções de baixa utilidade ou performance. Mal sabia eu que estive equivocado esse tempo todo.

Os greedy algorithms são fundamentais nos estudos de algoritmos e otimizações, não à toa o mundo acadêmico faz questão de mencioná-los em uma variedade de cursos de algoritmos ou de computação. Mas algumas definições podem passar uma ideia equivocada sobre o que eles realmente são, e do que são capazes.

Definição

Embora a Wikipedia possua uma definição interessante sobre o assunto, foi no GeeksforGeeks que encontrei uma passagem bem esclarecedora:

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to global solution are best fit for Greedy.

O Paulo Feofiloff vai além em "Algoritmos gulosos":

Para resolver um problema, um algoritmo guloso escolhe, em cada iteração, o objeto mais apetitoso que vê pela frente. (...) 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.

A estratégia gulosa tem por abordagem encontrar a melhor resposta para cada passo, sem se importar em resolver esse passo novamente ou com os passos seguintes, esperando como consequência um resultado global ótimo. Acabamos por ter algoritmos mais simples e intuitivos em grande parte dos casos, mas não necessariamente apresentando a melhor resposta.

As propriedades desse paradigma podem lembrar outras formas de escrever algoritmos, portanto, é importante saber diferenciá-lo.

Greedy não é brute-force

É bom deixar claro que um algoritmo guloso não é um algoritmo de força bruta:

• Greedy significa que o algoritmo, a cada passo, seleciona a melhor opção para aquele passo;
• Brute-force significa que o algoritmo seleciona uma opção de uma maneira mais simples, óbvia ou direta. E que repete essa tentativa até encontrar o resultado esperado.

Greedy não é naive

Essa talvez tenha sido a origem da minha confusão. Naive algorithms são de certa forma o primeiro passo para quando você está tentando resolver um problema complexo: Primeiro faça funcionar, depois faça melhor.

Em uma abordagem naive, não estamos necessariamente tentando resolver cada passo com a melhor opção possível, e sim tentando resolver o todo de maneira ingênua, sem nenhuma estrutura de dados rebuscada ou cálculo preparatório, e sem se preocupar com a performance do algoritmo em si.

Naive vs. Brute-force vs. Greedy

Uma maneira mais interessante de compreender como escrevemos um algoritmo com essas diferentes práticas é através do Knapsack Problem. Nesse famoso problema temos um conjunto de itens, cada qual com seu determinado peso e valor, e temos por desafio colocar o maior valor possível dentro de uma mochila com um determinado limite de peso.

• Um exemplo do método naive seria pegarmos os itens mais leves e colocarmos na bolsa até não haver mais espaço;
• Com brute-force, testaríamos todas as combinações de itens até chegar ao valor máximo para o limite de peso da bolsa;
• Já com o paradigma greedy, por intuição, pegaríamos primeiro os itens mais valiosos, até atingirmos o peso total da bolsa.

Todas as três formas chegam a um resultado. É possível afirmar que a primeira e última opção terão performance semelhantes, mas não necessariamente chegarão a um resultado ótimo. Encontrar o melhor resultado através da forma bruta, nesse problema, não é a melhor solução.

Qual o melhor uso de greedy algorithms?

Segundo o Brilliant.org, se as propriedades abaixo forem verdadeiras, pode-se aplicar a abordagem greedy para resolução do problema:

• Uma solução global ótima pode ser atingida ao escolher a opção ótima de cada passo;
• Um problema tem uma subestrutura ótima se uma solução ótima para o problema global conter as soluções ótimas para os sub-problemas.

Em outras palavras:

(...) greedy algorithms work on problems for which it is true that, at every step, there is a choice that is optimal for the problem up to that step, and after the last step, the algorithm produces the optimal solution of the complete problem.

Algoritmos como Huffman Code e Dijkstra's Shortest Path são greedy algorithms famosos que cumprem muito bem o seu papel. O GeeksforGeeks lista uma porção de outros algoritmos e problemas que utilizam o paradigma com sucesso. Um muito comum em entrevistas de emprego é o Minimum Swaps for Bracket Balancing.

Considerações finais

Compreendendo a diferença entre um greedy e um naive algorithm, fica mais fácil entender quando utilizar uma técnica ou outra. Uma abordagem ingênua funciona bem quando estamos começando a construir o algoritmo que solucionará um problema. De forma iterativa podemos melhorá-lo, até chegar aos valores de performance desejados.

Uma abordagem greedy pode trazer resultados satisfatórios para a sua solução, mas nem sempre trará o melhor resultado. Caso as propriedades listadas acima se apliquem ao algoritmo que você procura, sem dúvida nenhuma é uma técnica que, além de lhe ajudar a escrever um solução mais intuitiva, te trará os resultados esperados.

Se você ficou curioso sobre como resolver o Knapsack Problem de forma ótima, há a opção de utilizar Dynamic Programming, outro paradigma que tem certa semelhança com greedy algorithms, e que vamos falar sobre em outro post. Uma alternativa mais simples e intuitiva (e greedy) é criar uma terceira variável que armazene peso / valor e utilize esse valor no processo de ordenação (exemplo).

Até a próxima.

Referências

• Brilliant - Greedy algorithms
• Data Structures and Algorithms with Object-Oriented Design Patterns in C++ - Brute-Force and Greedy Algorithms
• GeeksforGeeks - Greedy algorithms
• Smart Grid - Brute Force/Naive/Greedy algorithm
• Stackoverflow - Why selection sort is not greedy?
• USP - Algoritmos gulosos
• Wikipedia - Greedy algorithm