Algoritmos Gulosos: Estratégias Heurísticas, Problema do Troco e Escalonamento

1. O que são Algoritmos Gulosos: Filosofia do Momento Presente

Na teoria da computação, um Algoritmo Guloso (Greedy Algorithm) é um paradigma de resolução de problemas baseado em um princípio simples e direto: em cada etapa do processo de decisão, escolha a opção que parece mais atraente, rentável ou eficiente no momento presente, sem se preocupar com as consequências futuras ou decisões passadas.

Ao contrário de estratégias que calculam todas as ramificações possíveis ou que voltam atrás quando encontram um obstáculo, o algoritmo guloso é obstinado: ele faz sua escolha ótima local, adiciona o item à solução final e jamais reavalia essa decisão. Se essa sequência de escolhas míopes locais convergir para a melhor solução global possível, dizemos que o problema é solucionável de forma gulosa.

A grande vantagem desse paradigma é a sua velocidade espantosa. Enquanto algoritmos de força bruta podem levar anos para calcular combinações exponenciais de escolhas, algoritmos gulosos tipicamente resolvem o mesmo problema em tempo linear (mathcal{O}(N)) ou quase-linear (mathcal{O}(N log N)).

2. Os Dois Pilares: Escolha Gulosa e Subestrutura Ótima

Nem todo problema de otimização pode ser resolvido com uma abordagem gulosa. Para que um algoritmo guloso produza com rigor matemático a melhor solução global de um problema, duas propriedades fundamentais devem ser satisfeitas:

1. Propriedade da Escolha Gulosa (Greedy Choice Property): Demonstra que uma solução global ótima pode ser alcançada fazendo escolhas locais imediatas. Em outras palavras, não é necessário considerar os resultados dos subproblemas futuros para decidir a primeira ação: você pode tomar a melhor decisão agora e resolver o restante do problema que sobrou depois.
2. Subestrutura Ótima (Optimal Substructure): Um problema exibe subestrutura ótima se a solução ideal para o problema inteiro contiver em si as soluções ideais para os seus subproblemas. Por exemplo, se o menor caminho rodoviário de São Paulo a Salvador passa por Belo Horizonte e Vitória da Conquista, então o trecho entre Belo Horizonte e Vitória da Conquista deve ser, obrigatoriamente, o menor caminho possível entre essas duas cidades.

Se um problema não possuir a propriedade da escolha gulosa, tomar a melhor decisão imediata levará a um beco sem saída subótimo. Nesses casos, precisamos recorrer a Programação Dinâmica ou Backtracking.

3. O Clássico Problema do Troco de Moedas (Coin Change)

O exemplo didático mais famoso do paradigma guloso é o Problema do Troco de Moedas: dado um valor numérico inteiro (V) e um conjunto de moedas com valores disponíveis ({M_1, M_2, dots, M_k}), qual é o menor número possível de moedas necessárias para somar exatamente (V)?

A estratégia gulosa dita a seguinte regra:

• Ordene as moedas em ordem decrescente de denominação.
• Para cada moeda, pegue o máximo possível dessa moeda que não ultrapasse o saldo restante do troco.
• Subtraia o valor correspondente do saldo e repita para a próxima moeda disponível.
• O processo termina quando o saldo chegar a zero.

4. Implementação do Algoritmo de Troco Guloso em logicabr.dev

Abaixo está a implementação completa e robusta do algoritmo guloso de troco utilizando a sintaxe oficial do logicabr.dev:

// Sistema monetario ordenado de forma decrescente
vetor moedas = [100, 50, 20, 10, 5, 2, 1];
numero totalMoedasDisponiveis = 7;

funcao calcularTrocoGuloso(numero valorTotal) {
  saida("========================================");
  saida("PROCESSANDO TROCO PARA: R$ " + valorTotal);
  saida("========================================");

  numero restante = valorTotal;
  numero contagemTotalItens = 0;

  para (numero i = 0; i < totalMoedasDisponiveis; i++) {
    numero valorMoeda = moedas[i];

    // Escolha gulosa: pega a quantidade maxima da maior moeda possivel
    se (restante >= valorMoeda) {
      numero qtd = 0;
      enquanto (restante >= valorMoeda) {
        qtd = qtd + 1;
        restante = restante - valorMoeda;
      }
      contagemTotalItens = contagemTotalItens + qtd;
      saida("-> Cedula/Moeda R$ " + valorMoeda + ": " + qtd + " unidade(s)");
    }
  }

  saida("----------------------------------------");
  saida("Total minimo de itens entregues: " + contagemTotalItens);
  saida("Saldo pendente nao pago: R$ " + restante);
  saida("========================================");
  retorno contagemTotalItens;
}

// Execucoes de teste
calcularTrocoGuloso(88);
calcularTrocoGuloso(286);

5. Teste de Mesa e Auditoria de Estados Passo a Passo

Vamos acompanhar a execução passo a passo do algoritmo para o valor de entrada R$ 88 no simulador de memória:

Resultado Final da Auditoria: Para entregar R$ 88, foram necessárias exatamente 6 peças monetárias: 1x50, 1x20, 1x10, 1x5, 1x2 e 1x1. O algoritmo operou com precisão cirúrgica sem retroceder em nenhuma escolha.

6. Escalonamento de Tarefas e Seleção de Atividades (Interval Scheduling)

Outro clássico indiscutível onde a abordagem gulosa atinge a perfeição matemática é o problema do Escalonamento de Intervalos (Activity Selection Problem).

Imagine uma sala de reuniões disputada por várias equipes. Cada reunião possui um horário de início e um horário de término. Duas reuniões não podem ocorrer no mesmo horário. Como selecionar o maior número possível de reuniões compatíveis?

Existem vários critérios intuitivos que falham:

• Escolher a reunião mais curta primeiro? Pode falhar ao bloquear reuniões adjacentes.
• Escolher a que começa mais cedo? Pode começar cedo e durar o dia inteiro, impedindo todas as outras.

A Escolha Gulosa Comprovadamente Ótima: Ordene as reuniões pelo horário de término (quem termina mais cedo). Escolha sempre a primeira reunião que termina mais cedo e, sucessivamente, selecione a próxima reunião compatível cujo horário de início seja maior ou igual ao término da anterior.

// Tarefas ordenadas pelo horario de termino
vetor nomesTarefas = ["Daily Standup", "Design Review", "Alinhamento Sprint", "Treinamento TI", "Demo do Cliente"];
vetor horaInicio = [9, 10, 11, 13, 15];
vetor horaFim =    [10, 12, 13, 15, 17];
numero totalTarefas = 5;

funcao escalonarReunioes() {
  saida("=== ESCALONAMENTO DE ATIVIDADES GULOSO ===");
  numero selecionadas = 0;
  numero ultimoFim = 0;

  para (numero i = 0; i < totalTarefas; i++) {
    se (horaInicio[i] >= ultimoFim) {
      saida("[APROVADA]: " + nomesTarefas[i] + " (" + horaInicio[i] + "h as " + horaFim[i] + "h)");
      ultimoFim = horaFim[i];
      selecionadas = selecionadas + 1;
    } senao {
      saida("[RECUSADA (CONFLITO)]: " + nomesTarefas[i]);
    }
  }

  saida("Total de salas alocadas com sucesso: " + selecionadas);
}

escalonarReunioes();

7. Onde o Guloso Falha: O Limite Entre Greedy e Programação Dinâmica

A maior armadilha intelectual de um programador júnior é achar que o algoritmo guloso funciona para tudo. Vejamos um contraexemplo clássico onde a estratégia gulosa produz uma resposta errada:

Fundamentos de Arquitetura e Impacto no Hardware da CPU

Para compreender verdadeiramente a performance de um algoritmo em ambientes modernos, não basta analisar apenas a contagem de instruções no papel. A arquitetura dos processadores atuais (x86-64 e ARM) baseia-se em hierarquias complexas de memória: registradores ultra-rápidos, caches L1 (instruções e dados), L2, L3 e finalmente a memória RAM principal.

Quando executamos Hardware, Ordenação e Desempenho de Algoritmos Gulosos, o comportamento do circuito de Branch Prediction (predição de saltos condicionais) da CPU desempenha um papel determinante. Cada desvio condicional (como um comando se ou condição de laço enquanto) que não pode ser previsto com precisão pela CPU provoca uma descarga da esteira de instruções (pipeline stall), descartando ciclos preciosos de processamento.

Algoritmos gulosos são extremamente velozes porque operam em um único loop sequencial O(N). No entanto, quase todos os algoritmos gulosos exigem que a massa de dados inicial esteja previamente ordenada com base no fator de ganho (heurística). Essa ordenação preliminar impõe um custo de O(N log N) utilizando Quicksort ou Mergesort.

Do ponto de vista de arquitetura de CPU, uma vez ordenados os vetores, o loop guloso desfruta de um padrão de acesso à memória estritamente linear e contíguo. Isso maximiza o acerto no cache L1 de dados, permitindo que a unidade de prefetch de hardware traga centenas de elementos vizinhos antecipadamente.

Do ponto de vista da física da computação, a localidade espacial e temporal de referência é outro fator crítico: percorrer a memória em posições contíguas sequenciais permite que o mecanismo de Hardware Prefetching da CPU antecipe os próximos blocos de dados antes mesmo de serem solicitados pelo código, carregando linhas inteiras de cache (tipicamente 64 bytes) sem penalidade de latência.

Demonstração Matemática Rigorosa da Eficiência Assintótica

A análise teórica desenvolvida pela ciência da computação formal permite prever o comportamento exato do algoritmo quando o volume de dados (N) cresce exponencialmente em direção ao infinito:

Além disso, como o algoritmo guloso nunca faz backtracking ou recursão profunda, a pilha de execução (Call Stack) permanece em O(1), eliminando qualquer risco de Stack Overflow e mantendo o consumo de memória fixo.

Essa dedução algébrica formal comprova por que a intuição superficial frequentemente engana programadores juniores. Saber classificar formalmente as curvas de crescimento assintótico separa o amador do engenheiro de software qualificado para arquitetar sistemas de alta escala que atendem milhões de usuários simultâneos sem lentidão.

9. Demonstração Formal: Sistemas de Moedas Canônicos e Matróides

Na ciência da computação formal, a condição necessária e suficiente para que problemas combinatórios gulosos garantam a resposta ótima reside na Teoria dos Matróides, formulada pelo matemático Hassler Whitney e expandida por Jack Edmonds.

Um matróide é uma estrutura combinatória que generaliza o conceito de independência linear de espaços vetoriais. Se um problema puder ser mapeado em um matróide ponderado, está matematicamente provado que o Algoritmo Guloso encontra sempre o peso máximo ou mínimo global.

No caso de sistemas de moedas, um conjunto monetário é denominado canônico quando o algoritmo guloso produz a contagem mínima de moedas para todo e qualquer valor inteiro (V > 0). David Pearson publicou em 1994 um algoritmo em (mathcal{O}(k^3)) que testa se qualquer conjunto arbitrário de (k) moedas é canônico ou não.

10. Aplicações no Mundo Real: Compressão Huffman, Dijkstra e Kruskal

Alguns dos algoritmos mais importantes e premiados da história da engenharia de software utilizam o paradigma guloso:

• Algoritmo de Huffman (Compressão de Dados): Cria códigos binários de tamanho variável para caracteres com base na frequência com que aparecem. É a base do formato ZIP, GZIP e da compressão de imagens JPEG.
• Algoritmo de Dijkstra (Menor Caminho em Grafos): Em cada passo, escolhe o vértice não visitado com menor distância acumulada até a origem. Utilizado em chips de GPS automotivos e no roteamento de pacotes OSPF na internet.
• Algoritmo de Kruskal e Prim (Árvore Geradora Mínima): Seleciona gulosamente as arestas mais baratas de uma rede que não fechem ciclos. Utilizado no planejamento de cabeamento elétrico, adutoras de saneamento e redes de fibra óptica submarinas.
• Escalonamento de CPUs em Sistemas Operacionais (Shortest Job First): Atribui o processador à tarefa mais curta da fila para minimizar o tempo médio de espera no sistema.

11. Os 5 Erros Críticos ao Implementar Algoritmos Gulosos

Evite estes equívocos comuns que custam caro em entrevistas técnicas e na produção:

12. Projeto Prático: Otimizador de Troco e Cédulas para PDV em logicabr.dev

Vamos consolidar o conhecimento construindo um Módulo de Frente de Caixa Inteligente com contabilidade de estoque limitado de cédulas:

vetor notasDisponiveis = [100, 50, 20, 10, 5, 2];
vetor estoqueNotas =     [5,   10, 8,  15, 20, 30]; // Quantidade em estoque
numero totalDenominacoes = 6;

funcao dispensarTrocoComEstoque(numero valorVenda, numero valorPago) {
  saida("================================================");
  saida("     TERMINAL DE PONTO DE VENDA (PDV)           ");
  saida("================================================");
  saida("Valor da Compra: R$ " + valorVenda);
  saida("Valor Entregue pelo Cliente: R$ " + valorPago);

  se (valorPago < valorVenda) {
    saida("[ERRO]: Pagamento insuficiente! Faltam R$ " + (valorVenda - valorPago));
    retorno falso;
  }

  numero trocoDevido = valorPago - valorVenda;
  saida("Troco a ser Devolvido: R$ " + trocoDevido);

  se (trocoDevido == 0) {
    saida("[SUCESSO]: Pagamento exato, sem troco devido.");
    retorno verdadeiro;
  }

  numero saldo = trocoDevido;
  vetor notasEntregues = [0, 0, 0, 0, 0, 0];

  para (numero i = 0; i < totalDenominacoes; i++) {
    numero valorNota = notasDisponiveis[i];

    enquanto (saldo >= valorNota e estoqueNotas[i] > 0) {
      saldo = saldo - valorNota;
      estoqueNotas[i] = estoqueNotas[i] - 1;
      notasEntregues[i] = notasEntregues[i] + 1;
    }
  }

  se (saldo > 0) {
    saida("[FALHA DE CAIXA]: Nao ha cedulas suficientes em estoque para R$ " + saldo);
    retorno falso;
  }

  saida("------------------------------------------------");
  saida("DISPENSADOR DE CEDULAS:");
  para (numero i = 0; i < totalDenominacoes; i++) {
    se (notasEntregues[i] > 0) {
      saida("  -> Entregar " + notasEntregues[i] + " nota(s) de R$ " + notasDisponiveis[i]);
    }
  }
  saida("------------------------------------------------");
  saida("[STATUS]: Troco dispensado com sucesso absoluto!");
  retorno verdadeiro;
}

dispensarTrocoComEstoque(142, 200); // Troco R$ 58
dispensarTrocoComEstoque(35, 100);  // Troco R$ 65