Estes slides constituem um roteiro prático para entender, aplicar e analisar Algoritmos Gulosos (Greedy Algorithms), com ênfase em:
São heurísticas muito utilizadas na solução de problemas combinatórios e de otimização.
O objetivo é encontrar uma solução viável que maximize ou minimize uma função objetivo no vasto espaço de busca.
“Come e nunca vomita.”
A principal característica é: a cada decisão, o algoritmo sempre faz a escolha que parece mais promissora naquele exato instante. Ele toma atitudes míopes e imediatistas (como o Pac-Man devorando a pastilha mais próxima).
Um algoritmo guloso constrói uma solução etapa por etapa, baseando-se em duas premissas vitais:
Normalmente, um algoritmo guloso opera sob cinco componentes lógicos:
[!TIP] A chave para um algoritmo guloso funcionar rápido e bem está em ordenar corretamente os dados de entrada. A ordenação cria o critério pelo qual o algoritmo vai “devorar” as opções.
Geralmente o tempo total da nossa execução é dominado pela ordenação: \(\Theta(N \log N)\) para ordenar, seguido de uma passada Linear \(O(N)\) montando as respostas.
Problema (O Posto de Gasolina): Temos uma rede e precisamos de \(d\) litros (\(Demanda\)). Temos \(n\) fornecedores (candidatos). Cada fornecedor suporta um estoque \(E_i\) e cobra um preço \(P_i\) por litro.
Objetivo: Suprir a demanda \(d\) gastando o mínimo possível.
import java.util.*;
class Fornecedor { double preco, estoq; }
public class PostosGasolina {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
double d = sc.nextDouble();
Fornecedor[] forn = new Fornecedor[n];
for (int i = 0; i < n; i++) {
forn[i] = new Fornecedor();
forn[i].preco = sc.nextDouble();
forn[i].estoq = sc.nextDouble();
}
// Critério Guloso: ordenar pelo Menor Preço
Arrays.sort(forn, Comparator.comparingDouble(f -> f.preco));
double custo = 0.0;
for (int i = 0; i < n && d > 0; i++) {
if (forn[i].estoq < d) { // Devora o fornecedor todo
custo += forn[i].estoq * forn[i].preco;
d -= forn[i].estoq;
} else { // Pega o restinho e finaliza
custo += d * forn[i].preco;
d = 0;
}
}
if (d > 0) System.out.println("Impossivel");
else System.out.printf(Locale.US, "%.2f\n", custo);
}
}Como gerenciar atividades conflitantes que usam um mesmo recurso?
Objetivo: Atender o MÁXIMO de pessoas possíveis. (Não importa se a consulta dura 10 min ou 3 horas).
Qual heurística (critério) o dentista deve usar sempre que escolher quem entra na sala?
Podemos organizar os pacientes da agenda de diversas maneiras para tentar o ótimo. Vamos testar três abordagens puramente gulosas.
Regra: Atender quem chegou mais cedo.
Exemplo: * Joana: 08 às 18h * João: 09 às 10h * Maria: 11 às 12h * Pedro: 14 às 15h
Resultado: Joana tranca a cadeira até 18:00. João, Maria e Pedro vão embora. Total: 1 atendido. ➡️ Falhou miseravelmente.
Regra: Atender a consulta mais rápida primeiro.
Exemplo: * Lucas: 09h às 12h (3h) * Bia: 11h às 13h (2h) * Carlos: 12h às 15h (3h)
Resultado: Atendemos a Bia (é a mais rápida). Mas o horário dela fica bem no meio e bloqueia Lucas e Carlos. Total: 1 atendido. ➡️ Métrica falha.
Regra Definitiva: Sempre atenda quem vai devolver a sua cadeira mais rápido! (Menor término).
O critério de priorizar o término mais cedo nunca quebra a chance de atendimentos futuros, garantindo matematicamente a solução ótima verdadeira!
import java.util.*;
class Compromisso { int ini, fim; }
public class DentistaOBI {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Compromisso[] consulta = new Compromisso[n];
for (int i = 0; i < n; i++) {
consulta[i] = new Compromisso();
consulta[i].ini = sc.nextInt();
consulta[i].fim = sc.nextInt();
}
// Critério Guloso Vital: Ordenar pelo Término mais rápido
Arrays.sort(consulta, Comparator.comparingInt(c -> c.fim));
int livre = 0, qtd = 0;
for (int i = 0; i < n; i++) {
if (consulta[i].ini >= livre) { // A consulta inicia após o relógio livre?
qtd++; // Se sim, atenda!
livre = consulta[i].fim; // Estarei ocupado até o fim dessa consulta
}
}
System.out.println(qtd);
}
}Tome cuidado: Algoritmos gulosos são rápidos e simples, mas nem sempre encontram o ótimo global. Às vezes a sua “esperteza” de curto prazo leva você a um beco sem saída financeiro.
O clássico de Engenharia para provar o “Erro do Guloso” é o Problema da Mochila (Knapsack Problem).
Regras Básicas: * Você acha uma mochila que aguenta até \(W\) kg de carga. * Na sua frente há dezenas de tesouros, com diferentes Pesos e Valores. * Objetivo: Lotar sua maleta para que a soma do Valor (\(Custo\)) roubado seja o Absoluto MÁXIMO!
A Lógica Gulosa Míope: Pense como logista! “Vou levar tudo que tiver a melhor densidade monetária”. Cálculo: \(Raz\tilde{a}o = {Valor\ total \over Peso\ do\ objeto}\)
Se estamos lidando com a Mochila Fracionária, significa que os itens são pó de ouro, farinha, areia de prata (Podem ser partidos na metade!).
Mochila 0-1: Itens agora são indestrutíveis. Ou levamos a Televisão toda ou deixamos! (Binário). O fracionamento acaba, e o Guloso cai num abismo ao tentar otimizar.
Considere sua Mochila com limite de 50 kg: * Item 1: Pesa \(10\), Custa \(\$60\). (\(Raz\tilde{a}o = 6\ \$\) por Kilo) * Item 2: Pesa \(20\), Custa \(\$100\). (\(Raz\tilde{a}o = 5\ \$\) por Kilo) * Item 3: Pesa \(30\), Custa \(\$120\). (\(Raz\tilde{a}o = 4\ \$\) por Kilo)
Vamos ligar o Guloso sob esses parâmetros…
Ação do Algoritmo Míope: Pega Item 1 (Sobram 40kg). Pega Item 2 (Sobram 20kg). Tenta o Item 3 mas ele pesa 30kg. O Guloso tranca a mochila e chora. Lucro Míope: 160.
Realidade (O Ótimo): Deixar o famoso “Item 1” pra trás. O espaço exato de 50kg absorveria o Item 2 + Item 3. Lucro Verdadeiro: 220!
Como fundir dezenas de listas em uma só sem a CPU “gritar”? A fusão linear custa \(|A| + |B| - 1\) operações.
Se temos os vetores \(V_1=15, V_2=10 e V_3=5\): A ordem em que unimos dita tudo na CPU: - Opção Aleatória: \(V_1+V_2 \implies 25\). Depois \(25+V_3 \implies 30\). Total opções = 53 operações. - Abordagem Gulosa: Sempre extraia os dois menores disponíveis e os funda. - Mescla Rápida (Gulosa): \(V_2+V_3 \implies 15\). Depois \(15+V_1 \implies 30\). Total operado = 43 operações!
| Vantagens | Desvantagens |
|---|---|
| Simplicidade Extrema (\(Sort()\) + Loop). | Total dependência de “acertar” com a métrica da ordenação escolhida. |
| Mais rápidos na indústria! Complexidade travada em \(O(N\log N)\). | Vão perder em problemas sem Subestrutura Ótima. Podem te guiar ao abismo |
| Ideal para limites numéricos massivos. | Sem backtracking, eles deixam a inteligência “cega” ao passado ou aos erros cometidos. |
Essa filosofia resolveu inúmeros pilares da Engenharia da Computação: