Algoritmos Gulosos (Greedy Algorithms)

Um algoritmo guloso é um paradigma de resolução de problemas que constrói uma solução etapa por etapa, sempre escolhendo a alternativa que parece mais promissora naquele instante.

A principal premissa de um algoritmo guloso é: a cada passo, tomamos a decisão localmente ótima na esperança de que esse acúmulo de decisões imediatas leve inevitavelmente a uma solução globalmente ótima.

Analogia Prática: “Come e nunca devolve”. Um algoritmo guloso estrito não pratica backtracking (não revê escolhas passadas). Uma vez que um candidato entra na solução, ele fica. Uma vez descartado, ele jamais é reavaliado.

Características Essenciais

Para que uma estratégia gulosa realmente atinja o ótimo (e não uma “ilusão” sub-ótima), o problema em questão geralmente precisa exibir duas propriedades fundamentais:

Subestrutura Ótima: Como em Programação Dinâmica, a solução ótima do problema principal contém e baseia-se nas soluções ótimas de seus subproblemas.
Propriedade da Escolha Gulosa: Podemos montar a solução ótima definitiva unindo a nossa “primeira escolha gulosa” ao restante da resolução.

O Segredo: A Função de Seleção

Muitas vezes, a inteligência do algoritmo guloso não está num laço complexo de repetições, mas sim na ordenação correta dos dados de entrada (a famosa função de seleção).

Se ordenarmos os candidatos corretamente sob alguma lógica (maior valor, menor custo, maior razão), o algoritmo simplesmente varre a lista escolhendo quem vier primeiro.

Exemplo 1: Seleção de Atividades

O Problema: Imagine que temos várias atividades (palestras num evento, por exemplo) que querem usar a mesma sala. Cada atividade possui um horário para iniciar e um horário para terminar. Nosso objetivo é organizar a sala para sediar o maior número possível de atividades (não ter sobreposição).

Que regra gulosa garante que preencheremos a sala ao máximo?

Tentativa 1 (Mais cedo inicia): Escolher as que começam primeiro. Se uma palestra começar 08h e terminar 20h, ela travou o dia todo e perdemos tempo! (Sub-ótimo).
Tentativa 2 (Sessões Curtas): Escolher as que duram menos tempo. Pode ser que tenhamos uma palestra curtíssima do meio dia às 13h, empedindo duas grandes que fariam 09h-12h e 13h-16h. (Sub-ótimo).
Tentativa 3 (Correta): Escolher as que terminam primeiro!.

Se formos guloso e sempre alocarmos o espaço para finalizar as coisas o mais rápido possível no tempo, deixamos “mais fatias livres do restante do relógio” para as demais.

Visualização de Seleção

Implementação em C++

Vamos aplicar essa premissa. Criaremos um tipo (Struct) e ordenaremos pelo término usando as bibliotecas padrão do C++ <algorithm> e garantiremos nossa corretude via testes de asserção:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

struct Atividade {
    int inicio, fim, id;
};

// 1. A Regra Gulosa: quem termina primeiro avaliamos primeiro
bool ordenarPorFim(const Atividade &a, const Atividade &b) {
    return a.fim < b.fim;
}

int selecaoGulosa(std::vector<Atividade>& atividades) {
    if(atividades.empty()) return 0;

    // Ordenando N elementos leva O(N log N)
    std::sort(atividades.begin(), atividades.end(), ordenarPorFim);

    int count = 1; // A primeira após ordenação entra sempre
    int fimUltimaAdicionada = atividades[0].fim;

    // Varrendo os escolhidos O(N)
    for(int i = 1; i < atividades.size(); i++) {
        // Se a atual inicia AFTER ou JUNTO da minha última terminada
        if(atividades[i].inicio >= fimUltimaAdicionada) {
            count++;
            fimUltimaAdicionada = atividades[i].fim; // Atualiza o "relógio"
        }
    }
    return count;
}

void executando_testes() {
    std::vector<Atividade> lista = {
        {1, 4, 1}, {3, 5, 2}, {0, 6, 3}, {5, 7, 4},
        {3, 8, 5}, {5, 9, 6}, {6, 10, 7}, {8, 11, 8},
        {8, 12, 9}, {2, 13, 10}, {12, 14, 11}
    };
    
    // A seleção perfeita aqui nos dá máximo de 4 atividades agrupáveis
    assert(selecaoGulosa(lista) == 4);
    
    std::cout << "[✅] Testes Gulosos de Atividades passaram.\n";
}

int main() {
    executando_testes();
    return 0;
}

A complexidade final foi governada puramente pela ordenação, se fechando num belíssimo \(O(N \log N)\).

Exemplo 2: O Problema da Mochila (Knapsack Problem)

Um ladrão invade uma casa carregando uma mochila. A mochila suporta até uma certa Capacidade W quilos estritos. Na casa há dezenas de diferentes objetos, cada um contendo seu “peso” (wᵢ) físico e um “valor monetário” agregado (vᵢ).

Qual combinação de objetos se deve levar e qual devemos deixar no chão para lucrar ao máximo?

Aqui, os Gulosos encontram um abismo, dependendo da classificação material do objeto! Cuidado:

Variante 1: Mochila Fracionária

Imagine que os itens são divisíveis como pó de ouro, grãos ou açúcar. Neste modelo contínuo/líquido, uma tática puramente gulosa produz o melhor resultado 100% ótimo.

A Regra Gulosa é simples: Calcule o custo/benefício (Razão: Valor / Peso). Liste-os do mais rentável para o menos rentável na proporção. Caminhe enchendo a sacola. Preencha os mais valiosos por grama integralmente primeiro. Quando não couber ele inteiro pois a mala está terminando, basta recortar matematicamente a “fração final” correspondente ao vácuo restante enchendo o pó total.

Variante 2: Mochila Inteira binária (0-1)

Agora os objetos só levam duas flags booleanas: Inteiro (1) ou Não levo (0). Não posso cortar uma barra de ouro sólida maciça pela metade sem ferramentário do jogo, também não quero levar um notebook cortado no meio (é valor morto). E agora?

A estratégia simples de “ordenar pela melhor média” falha terrivelmente em cenários justos. Um bloco massivo levemente abaixo de rendimento de um pequenininho ultra denso pode não caber se colocarmos o denso primeiro que trava limiares de pesagem em espaços vazios gigantes.

Importante: Quando nos deparamos com problemas exaustivos discretos de Mochila Inteira (0-1), a abordagem comutadora perde valência para métodos de Programação Dinâmica como vimos nas pastas de DP.

Exercícios Sugeridos

Ao praticar exercícios onde pedem minimizações por algoritmos em O(N log N), atire pedras nos Gulosos (identifique a função gulosa a partir de Sortings customizados):