Published

14/04/2026

Modified

01/04/2026

A seguir está uma extração em Markdown com o máximo de conteúdo possível do PDF ****. Preservei:

Isso gera um Markdown muito próximo do conteúdo completo da apostila, adequado para processamento automático, LLM, RAG ou Quarto.

Algoritmos Gulosos

Autor: Norton T. Roman

Apostila baseada no trabalho de:

  • Delano M. Beder
  • Luciano Digianpietri
  • David Matuszek
  • Marco Aurelio Stefanes
  • Nivio Ziviani

Algoritmos Gulosos

Algoritmos gulosos são aqueles que, a cada decisão:

  • sempre escolhem a alternativa que parece mais promissora naquele instante
  • nunca reconsideram essa decisão

Ou seja:

  • uma escolha que foi feita nunca é revista
  • não há backtracking
  • analogia humorística apresentada no slide:

“Come e nunca vomita”.

No slide (pág. 2) há também uma imagem de um jogo Pac-Man, ilustrando a ideia de decisões locais.

Alternativa mais promissora?

Depende do problema.

Depende também do objetivo:

  • maximizar algo
  • minimizar algo

Exemplos:

  • encontrar o caminho mais curto
  • minimizar o número de jogadas
  • maximizar algum valor acumulado

Para isso é necessário:

  • um modo de avaliar as opções
  • uma função de avaliação

Essa função indica qual alternativa vale mais, segundo o objetivo do problema.

Assim:

  • a escolha é feita por um critério guloso
  • isto significa tomar uma decisão localmente ótima

Características dos algoritmos gulosos

Para construir a solução ótima:

Existe um conjunto de candidatos.

Durante o algoritmo são formados dois conjuntos:

  1. candidatos escolhidos
  2. candidatos rejeitados

Além disso existem algumas funções importantes.

Funções típicas de um algoritmo guloso

Função de solução

Verifica se o conjunto atual de candidatos:

  • já constitui uma solução

Não verifica ainda se ela é ótima.

Função de viabilidade

Verifica se um conjunto de candidatos é viável.

Também não verifica otimalidade.

Função de seleção

Indica, em qualquer momento:

  • qual candidato restante é o mais promissor.

Função objetivo

Fornece o valor da solução encontrada.

Exemplo:

  • comprimento de um caminho
  • valor total de objetos selecionados

Observação:

Nos algoritmos gulosos essa função nem sempre aparece explicitamente no algoritmo.

Relação entre seleção e objetivo

Normalmente:

  • a função de seleção está relacionada à função objetivo

Se o objetivo é:

Maximizar

Seleciona-se:

  • o candidato que proporciona o maior ganho individual

Minimizar

Seleciona-se:

  • o candidato de menor custo

Um segredo dos algoritmos gulosos

Frequentemente:

A chave está em ordenar corretamente os dados de entrada.

Propriedade fundamental

O algoritmo guloso não muda de ideia.

Uma vez que um candidato é:

escolhido

  • ele permanece na solução para sempre

descartado

  • ele nunca mais é reconsiderado

Uso típico

Algoritmos gulosos são usados em:

  • problemas de otimização
  • resolvidos através de uma sequência de decisões

Importante:

  • nem sempre produzem a solução ótima

Apesar disso:

  • frequentemente produzem boas soluções

Quando um guloso funciona

Se for possível provar que:

a escolha gulosa + as escolhas anteriores → levam à solução ótima

Então:

  • o algoritmo guloso sempre produzirá a solução ótima

Ideia geral da estratégia gulosa

A estratégia é:

construir a solução etapa por etapa

Processo:

  1. Selecionar o melhor elemento disponível
  2. Verificar se ele é viável
  3. Se for viável → adicioná-lo à solução
  4. Caso contrário → descartá-lo

Após uma sequência de decisões:

  • a solução é obtida.

Propriedade importante:

cada elemento é examinado no máximo uma vez

Ingredientes chave

Para que um algoritmo guloso funcione bem são necessários:

Subestrutura ótima

Um problema possui subestrutura ótima se:

uma solução ótima contém soluções ótimas para seus subproblemas.

Propriedade gulosa

A solução ótima global pode ser construída a partir de:

uma sequência de escolhas localmente ótimas.

Exemplo clássico: Seleção de atividades

Problema:

  • existem várias atividades
  • todas querem usar o mesmo recurso (ex: sala de aula)

Cada atividade possui:

  • horário de início
  • horário de término

Restrição:

  • duas atividades não podem ocorrer ao mesmo tempo

Objetivo

Selecionar:

o maior conjunto possível de atividades compatíveis

Atividades compatíveis:

  • não possuem sobreposição de tempo

Tentativa 1

Critério guloso:

escolher atividades que começam primeiro

Resultado:

  • solução ruim

Exemplo apresentado no slide:

Selecionou:

3, 8, 11

Total:

3 atividades

Mas era possível selecionar:

1, 4, 8, 11

Total:

4 atividades

Tentativa 2

Critério guloso:

escolher atividades que duram menos tempo

Resultado:

Selecionou:

2, 8, 11

Total:

3 atividades

Ainda não é ótimo.

Tentativa 3 (correta)

Critério guloso:

escolher atividades que terminam primeiro

Resultado:

  • solução ótima

Essa estratégia pode ser provada matematicamente correta.

Algoritmo guloso para seleção de atividades

Entrada:

  • lista de atividades ordenadas por tempo de término

Processo:

Para cada atividade:

  • verificar se pode ser incluída na solução

A atividade considerada em cada passo é:

a que termina primeiro entre as restantes.

Implementação em Java

public class SelecaoDeAtividadesGuloso {

static int selecaoGulosa(int[] ini, int[] fim, int n){

int ultimaSelecionada = 0;
int selecionadas = 0;

if (n == 0) return 0;

// a primeira atividade é sempre selecionada
System.out.print("a" + 0 + " ");
selecionadas++;

for (int i = 1; i < n; i++)
    if (ini[i] >= fim[ultimaSelecionada]) {

        System.out.print("a" + i + " ");
        selecionadas++;
        ultimaSelecionada = i;

    }

System.out.println();

return selecionadas;

}

Dados de exemplo

// atividades ordenadas pelo campo fim

private static int[] inicio = {
1,3,0,5,3,5,6,8,8,2,12
};

private static int[] fim = {
4,5,6,7,8,9,10,11,12,13,14
};

private static int numeroDeAtividades = 11;

public static void main(String[] args){

int total = selecaoGulosa(inicio,fim,numeroDeAtividades);

System.out.println("Foram selecionadas "
 + total + " atividades.");

}

Exemplo: Problema da Mochila

Dados:

  • mochila com capacidade máxima
  • conjunto de objetos

Cada objeto possui:

  • peso
  • valor

Objetivo:

maximizar o valor total dentro da mochila.

Duas versões do problema

Mochila fracionada

Os objetos podem ser divididos.

Exemplo:

  • ouro em pó

Mochila 0-1 (binária)

Objetos não podem ser divididos.

Exemplo:

  • barras de ouro

Mochila fracionada

Pergunta:

Qual a melhor ordenação dos objetos?

Resposta:

Ordenar por:

valor/peso

em ordem decrescente.

Essa solução gulosa é ótima.

Algoritmo da mochila fracionada

  1. Ordenar os itens por valor/peso
  2. Começar pelo item de maior razão
  3. Colocar o máximo possível na mochila
  4. Passar para o próximo item

Pseudocódigo

W = capacidade da mochila

load = 0
i = 1

while (load < W) and (i <= n)

    if (wi <= (W - load))
        pegar todo o item i

    else
        pegar (W - load)/wi do item i

    load += peso adicionado

    i++

Exemplo numérico (slide)

Objetos:

objeto peso valor
1 10 60
2 20 100
3 30 120

Capacidade da mochila:

50

Razão valor/peso:

6 , 5 , 4

Solução gulosa:

  • item 1
  • item 2
  • 2/3 do item 3

Valor total:

$240

(visual mostrado na página 36)

Mochila binária (0-1)

Objetos não podem ser divididos.

Pergunta:

ordenar por valor/peso ainda funciona?

Resultado

Se aplicarmos o mesmo critério guloso:

Selecionamos:

item 1
item 2

Valor:

$160

Essa solução é ótima?

Não.

A solução ótima seria:

item 2
item 3

Valor:

$220

(conforme mostrado na figura da página 44).

Conclusão

Algoritmos gulosos:

✔ simples ✔ rápidos ✔ frequentemente produzem boas soluções

Mas:

❌ nem sempre produzem soluções ótimas

Especialmente em problemas como:

  • mochila 0-1

Se quiser, posso também gerar uma versão ainda melhor para processamento automático, por exemplo:

  • Markdown estruturado por slide
  • Markdown com metadados para RAG
  • dataset JSON por slide
  • versão Quarto (.qmd) para slides
  • versão com todas as imagens embutidas (ótima para material didático).
Back to top