Algoritmos Gulosos

Visão geral

Um algoritmo guloso (greedy algorithm) é uma técnica de projeto de algoritmos que constrói uma solução de forma incremental, fazendo uma sequência de escolhas em que cada escolha é localmente ótima segundo alguma regra (por exemplo, “escolha a menor aresta”, “pegue o intervalo que termina mais cedo”, “mescle os dois símbolos menos frequentes”). Uma vez feita uma escolha, ela normalmente nunca é revisitada.

Métodos gulosos são populares porque, em geral, são:

Simples de implementar
Rápidos (comumente (O(n \log n)) devido a ordenação ou filas de prioridade)
Com otimalidade demonstrável para uma classe importante de problemas (mas não todos)

Em contraste com Programação Dinâmica, algoritmos gulosos geralmente não exploram múltiplas alternativas nem mantêm tabelas de soluções de subproblemas. E, quando o guloso não é exatamente ótimo, ele frequentemente é usado como uma heurística (heuristic) ou como base para garantias em Algoritmos de Aproximação.

Algoritmos gulosos: a ideia-chave

Um algoritmo guloso tipicamente se parece com:

Comece com uma solução (parcial) vazia.
Selecione repetidamente o próximo elemento “melhor” por algum critério.
Adicione-o à solução se isso mantiver a solução viável (ou ajuste a viabilidade).
Pare quando a solução estiver completa.

Essa regra do “melhor próximo passo” é a escolha gulosa. A pergunta central é:

Quando uma sequência de escolhas localmente ótimas produz uma solução globalmente ótima?

Para responder, precisamos de condições de correção e técnicas de prova.

Quando o guloso é correto: propriedades e estratégias de prova

Algoritmos gulosos são corretos quando o problema tem estrutura que garante que escolhas locais podem ser estendidas até um ótimo global. Dois conceitos de correção amplamente usados são:

Propriedade da escolha gulosa: Existe uma solução ótima que começa com uma escolha gulosa.
Subestrutura ótima: Depois de fazer uma escolha, o problema restante tem a mesma forma, e uma solução ótima para o restante combina com a escolha para formar uma solução ótima no todo.

Subestrutura ótima sozinha não é suficiente (muitos problemas de programação dinâmica a têm, mas não são gulosos). O guloso também precisa da propriedade da escolha gulosa, que frequentemente é provada usando um argumento de troca ou uma estrutura de matroide.

Argumentos de troca (uma técnica de prova coringa)

Um argumento de troca (exchange argument) mostra que, para qualquer solução ótima (O), você pode “trocar” uma parte dela pela escolha gulosa (g) sem piorar a solução, produzindo outra solução ótima que inclui (g). Isso prova que se comprometer com (g) é seguro.

Modelo:

Seja (O) uma solução ótima.
Compare a primeira escolha do guloso (g) com a primeira escolha usada em (O).
Se (g \in O), pronto. Caso contrário, modifique (O) trocando algum(ns) elemento(s) por (g).
Prove que a viabilidade é preservada e que o valor da função objetivo não piora.
Conclua que existe uma solução ótima que começa com (g).
Recursione/itere.

Você verá esse padrão nas provas de escalonamento de intervalos e de árvore geradora mínima.

Propriedades de corte e ciclo (argumentos de troca específicos de grafos)

Para problemas em grafos, a correção do guloso é frequentemente mostrada usando lemas estruturais:

Propriedade de Corte da AGM: Para qualquer corte, a aresta mais leve que o atravessa é “segura” para incluir em uma AGM.
Propriedade de Ciclo da AGM: Em qualquer ciclo, a aresta mais pesada não pode pertencer a uma AGM (se os pesos forem distintos; de forma mais geral, existe uma AGM sem ela).

Esses são argumentos de troca especializados para árvores geradoras.

Matroides: um arcabouço geral em que o guloso é ótimo

Um matroide (matroid) é uma estrutura combinatória que generaliza independência linear (de espaços vetoriais) para conjuntos. Muitos problemas de “escolher elementos sob restrições de independência” formam um matroide, e o guloso torna-se comprovadamente ótimo.

Um matroide é um par ((E, \mathcal{I})) em que:

(E) é um conjunto finito de elementos.
(\mathcal{I}\subseteq 2^E) é uma coleção de conjuntos independentes que satisfaz:
1. Hereditariedade: Se (A \in \mathcal{I}) e (B \subseteq A), então (B \in \mathcal{I}).
2. Propriedade de troca: Se (A, B \in \mathcal{I}) e (|A| < |B|), então existe um elemento (x \in B \setminus A) tal que (A \cup {x} \in \mathcal{I}).

Teorema guloso (informal): Se o sistema de viabilidade é um matroide, então ordenar elementos por peso e adicionar repetidamente o próximo elemento que mantém o conjunto independente produz um conjunto independente de peso máximo.

Isso ajuda a explicar por que o guloso funciona para algumas tarefas do tipo “escolha um subconjunto sob restrições” e por que ele falha quando as restrições não satisfazem a troca de matroide.

Padrões gulosos comuns na prática

Algoritmos gulosos tendem a cair em alguns padrões recorrentes de implementação:

1) Ordenar por uma chave e então varrer

Exemplos: escalonamento de intervalos (ordenar por tempo de término), escalonamento para minimizar atraso (ordenar por datas de vencimento), AGM de Kruskal (ordenar arestas por peso).

Complexidade típica: (O(n \log n)) para ordenação + varredura quase linear.

2) Extrair repetidamente o melhor candidato (fila de prioridade)

Exemplos: codificação de Huffman (extrair duas menores frequências repetidamente), AGM de Prim (extrair aresta mínima conectante via heap).

Complexidade típica: (O(n \log n)) ou (O(m \log n)).

3) Manter a viabilidade com uma estrutura de dados

Exemplos: Kruskal usa união de conjuntos disjuntos (disjoint-set union, Union-Find) para evitar ciclos; escalonamento de intervalos apenas checa o último tempo de término; restrições de viabilidade mais complexas podem exigir estruturas especializadas.

4) Guloso como heurística (sem garantia de otimalidade)

Em muitos contextos de IA/ML, “guloso” significa “melhoria míope” (por exemplo, seleção progressiva de atributos, divisão em árvores de decisão). Isso pode ser eficaz, mas nem sempre é globalmente ótimo; muitas vezes é analisado como heurística ou via limites de aproximação.

Exemplo clássico: escalonamento de intervalos (número máximo de intervalos não sobrepostos)

Problema: Dados intervalos ([s_i, f_i)), selecione o número máximo de intervalos que não se sobrepõem.

Estratégia gulosa: Sempre escolher o intervalo com o término mais cedo dentre aqueles compatíveis com o que você já escolheu.

Por que “término mais cedo” funciona (intuição via argumento de troca)

Seja (g) o intervalo que termina primeiro. Considere qualquer solução ótima (O). Se (O) começa com um intervalo diferente (o) que termina depois de (g), troque (o) por (g). Isso não pode reduzir a quantidade de intervalos que você consegue escalonar depois, porque terminar mais cedo deixa pelo menos tanto espaço.

Implementação (estilo Python)

def interval_scheduling(intervals):
    # intervals: list of (start, finish)
    intervals = sorted(intervals, key=lambda x: x[1])  # sort by finish time
    chosen = []
    current_end = float("-inf")

    for s, f in intervals:
        if s >= current_end:
            chosen.append((s, f))
            current_end = f

    return chosen

Complexidade de tempo: (O(n \log n)) para ordenação; a varredura é (O(n)).
Usos práticos: alocação de recursos, agendamento de salas de reunião, seleção de janelas de tempo não sobrepostas para pipelines de rotulagem/anotação.

Exemplo clássico: codificação de Huffman (códigos prefixos ótimos)

Problema: Dadas frequências de símbolos, produza um código binário livre de prefixo (prefix-free) minimizando o comprimento esperado do código.

Estratégia gulosa: Mesclar repetidamente os dois símbolos/subárvores menos frequentes.

Isso produz um código ótimo, amplamente usado em compressão (por exemplo, DEFLATE usa componentes de codificação de Huffman).

Ideia-chave

Em um código prefixo ótimo, os dois símbolos menos frequentes podem ser tornados irmãos no nível mais profundo. A mesclagem gulosa de Huffman impõe exatamente essa estrutura.

Esboço de implementação (usando um heap mínimo)

import heapq

def huffman_cost(freqs):
    # freqs: list of positive numbers
    heap = freqs[:]
    heapq.heapify(heap)
    total = 0

    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        merged = a + b
        total += merged
        heapq.heappush(heap, merged)

    return total

Isso calcula o custo total do comprimento ponderado do caminho (equivalente ao número esperado de bits até um fator constante dependendo da normalização).

Complexidade de tempo: (O(n \log n)).
Relevância em IA/ML: Codificação de Huffman aparece no armazenamento e transmissão eficientes de artefatos de modelos e fluxos de tokens; também é conceitualmente relacionada à construção de árvores por mesclagem repetida (embora a maioria dos objetivos de agrupamento hierárquico em ML não seja resolvida pela regra de Huffman).

Exemplo clássico: árvores geradoras mínimas (AGM)

Problema: Dado um grafo conexo, ponderado e não direcionado, encontre uma árvore geradora com peso total mínimo.

Dois algoritmos gulosos canônicos resolvem AGM de forma ótima: Kruskal e Prim.

Algoritmo de Kruskal

Escolha gulosa: Adicionar arestas em ordem crescente de peso, pulando qualquer aresta que criaria um ciclo.

Estrutura de dados: Union-Find (Disjoint Set Union) para testar se dois vértices já estão conectados.

def kruskal_mst(n, edges):
    # n vertices labeled 0..n-1
    # edges: list of (w, u, v)
    edges.sort()

    parent = list(range(n))
    rank = [0] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return False
        if rank[ra] < rank[rb]:
            parent[ra] = rb
        elif rank[ra] > rank[rb]:
            parent[rb] = ra
        else:
            parent[rb] = ra
            rank[ra] += 1
        return True

    mst = []
    for w, u, v in edges:
        if union(u, v):
            mst.append((w, u, v))
            if len(mst) == n - 1:
                break
    return mst

Intuição de correção: Pela propriedade de corte, quando Kruskal considera uma aresta (e) que conecta dois componentes diferentes, (e) é a aresta mais leve cruzando aquele corte entre componentes e, portanto, é “segura”.

Complexidade de tempo: (O(m \log m)) devido à ordenação das arestas; Union-Find é quase linear (Ackermann inversa).

Algoritmo de Prim

Escolha gulosa: Crescer uma única árvore adicionando repetidamente a aresta de menor peso que conecta a árvore atual a um novo vértice.

Comumente implementado com uma fila de prioridade; roda em (O(m \log n)).

Relevância em IA/ML: AGMs aparecem em agrupamento (por exemplo, single-linkage clustering), aprendizado semissupervisionado baseado em grafos e na construção de estruturas esparsas para busca aproximada por similaridade (embora muitos sistemas modernos usem heurísticas especializadas de construção de grafos para ANN, em vez de AGM exata).

Um exemplo comum “quase guloso”: caminho mínimo de Dijkstra

O algoritmo de Dijkstra é frequentemente descrito como guloso: ele repetidamente finaliza o nó ainda não finalizado que está atualmente mais próximo. Ele é correto quando todos os pesos das arestas são não negativos, e sua correção também depende de um argumento de escolha gulosa segura.

Vale lembrar como um padrão: o guloso pode ser correto sob restrições específicas (aqui, não negatividade) e pode falhar caso contrário (arestas negativas exigem Bellman–Ford ou reponderação).

Guloso vs programação dinâmica (e quando preferir cada um)

Guloso e programação dinâmica podem parecer similares: ambos constroem soluções a partir de peças menores. A diferença é o comprometimento:

Guloso se compromete com uma escolha localmente ótima e nunca a revisita.
Programação dinâmica considera sistematicamente escolhas alternativas armazenando soluções ótimas para subproblemas.

Uma regra prática rápida:

Se você consegue provar uma propriedade da escolha gulosa (frequentemente via argumento de troca / matroide / propriedade de corte), o guloso é ideal.
Se o problema tem subestrutura ótima mas não há escolha local segura, programação dinâmica é mais apropriada. Veja Programação Dinâmica.

Guloso como aproximação e na prática de IA/ML

Muitos problemas de otimização em ML são grandes demais ou difíceis demais (NP-difíceis) para algoritmos exatos, e estratégias gulosas tornam-se ferramentas práticas.

Maximização submodular (uma grande área em que “guloso vence”)

Uma função de conjuntos (f(S)) é submodular (submodular) se tem retornos decrescentes: adicionar um elemento ajuda menos quando você já tem um conjunto grande. Para funções submodulares monótonas sob uma restrição de tamanho (|S| \le k), o algoritmo guloso simples (“adicione o item com o maior ganho marginal”) alcança uma aproximação comprovável de ((1 - 1/e)).

Esse arcabouço aparece em:

Seleção de subconjuntos de dados para treinamento
Sumarização e seleção em lote (diversidade + cobertura)
Heurísticas de aprendizado ativo (quando formuladas como objetivos submodulares)

Esses resultados normalmente são cobertos em Algoritmos de Aproximação, mas é útil reconhecer o guloso como o motor por trás de muitas garantias.

Heurísticas gulosas em sistemas comuns de ML (nem sempre ótimas)

Alguns procedimentos amplamente usados em ML são gulosos em espírito:

Árvores de decisão escolhem a divisão com a maior redução imediata de impureza; árvores globalmente ótimas são, em geral, intratáveis.
Seleção progressiva de atributos adiciona o atributo que mais melhora a pontuação de validação; pode ficar presa em ótimos locais.
Busca em feixe (beam search) na decodificação de sequências é uma variante heurística de largura limitada da decodificação gulosa.

Nesses casos, “guloso” é uma escolha de projeto pragmática: rápida, simples, frequentemente boa o bastante, mas sem garantia de otimalidade.

Como o guloso falha: reconhecendo armadilhas

O guloso falha quando a melhoria local não se alinha com a otimalidade global.

Modos comuns de falha:

Proxy errado do objetivo: escolher passos localmente mais baratos pode bloquear combinações melhores depois.
Restrições não-matroide: conjuntos viáveis não satisfazem troca; escolhas iniciais podem impedir construir um conjunto de tamanho/peso ótimo.
Necessidade de antecipação: problemas como mochila (0/1) ou sequências ótimas de edição exigem considerar trade-offs.

Um exemplo clássico de cautela é a mochila 0/1: escolher itens pela maior razão valor/peso é ótimo para a versão fracionária, mas não para 0/1.

Projetando um algoritmo guloso: um checklist prático

Quando você acha que uma abordagem gulosa pode funcionar:

Defina a regra de escolha gulosa claramente (o que você escolhe a seguir?).
Defina a viabilidade (quais restrições devem sempre valer?).
Tente provar a propriedade da escolha gulosa, frequentemente por:
- Argumento de troca
- Propriedade de corte/ciclo (grafos)
- Estrutura de matroide (sistemas de independência)
Prove a subestrutura ótima: após escolher (g), o restante é o mesmo tipo de problema.
Valide com contraexemplos: casos pequenos construídos que testam a regra de escolha.
Implemente com os primitivos corretos:
- Ordenação
- Filas de prioridade
- Union-Find
- Varreduras com dois ponteiros, etc.

Resumo

Algoritmos gulosos constroem soluções fazendo repetidamente escolhas localmente ótimas. Eles são rápidos e elegantes e, em muitos casos importantes, são comprovadamente corretos — especialmente quando a correção pode ser estabelecida por meio de argumentos de troca, propriedades de corte/ciclo ou do arcabouço mais geral de matroide.

Sucessos clássicos do guloso incluem:

Escalonamento de intervalos (término mais cedo)
Codificação de Huffman (mesclar os dois menos frequentes)
Árvores geradoras mínimas (Kruskal/Prim)

Em IA/ML, métodos gulosos aparecem tanto como ferramentas exatas (por exemplo, estruturas baseadas em AGM) quanto como heurísticas ou aproximações poderosas (por exemplo, árvores de decisão, seleção de subconjuntos). Saber quando o guloso é justificável — e como provar ou testar isso — é uma competência central no pensamento algorítmico para sistemas modernos de IA.