Projeto e Análise de Algoritmos  
Aula 04 Técnicas de Projeto de Algoritmos  
(Método Guloso)  
Edirlei Soares de Lima  
<edirlei@iprj.uerj.br>  
Estratégias de Projeto de Algoritmos  
Força Bruta (Brute Force)  
Dividir e Conquistar (Divide and Conquer)  
Diminuir e Conquistar (Decrease and Conquer)  
Transformar e Conquistar (Transform and Conquer)  
Compromisso TempoEspaço (Space and Time Tradeoffs)  
Estratégia Gulosa (Greedy)  
Programação Dinâmica (Dynamic Programming)  
Voltando Atrás (Backtracking)  
Ramificar e Limitar (Branch and Bound)  
Algoritmos Aproximados  
Método Guloso  
Ideia: quando temos uma escolha a fazer, fazemos aquela que  
pareça ser a melhor no momento.  
Ou seja, fazemos uma escolha ótima local, na esperança de obter uma  
solução ótima global.  
O método guloso sugere construir uma solução através de  
uma sequência de passos, cada um expandindo uma solução  
parcialmente construída até o momento, até uma solução  
completa para o problema ser obtida.  
Métodos gulosos nem sempre garantem soluções ótimas, mas quando  
eles garantem, geralmente são as soluções mais simples e eficientes.  
Método Guloso  
Em cada passo de um algoritmo guloso, a escolha  
deve ser:  
Possível: deve satisfazer as restrições do problema;  
Localmente ótima: deve ser a melhor escolha local dentre  
todas as escolhas disponíveis naquele passo;  
Irreversível: uma vez feita, ele não pode ser alterada nos  
passos subsequentes do algoritmo.  
Exemplo 1: Problema da Mochila  
Dados n itens:  
Pesos: w1, w2, ..., wn  
Valores: v1, v2, …, vn  
Uma mochila de capacidade W  
Problema: encontrar o subconjunto mais valioso de  
itens que caibam dentro da mochila (Knapsack  
Problem).  
Exemplo 1: Problema da Mochila  
Problema da Mochila 0-1:  
Um ladrão rouba uma loja que contém n itens: o item i  
tem peso wi e vale vi. Ele quer levar o maior valor possível  
em uma mochila de carga máxima W. Quais itens escolher?  
Problema da Mochila Fracionada:  
Mesmo formulação anterior, mas agora ele pode carregar  
frações dos itens, ao invés da escolha binária (0-1).  
Exemplo 1: Problema da Mochila  
Fracionada)  
(
Algoritmo Guloso (ideia):  
Ordene os itens por valor/peso (vi/wi);  
Começando em i = 1, coloque na mochila o máximo  
possível do item i que estiver disponível ;  
Se puder levar mais, passe para o próximo item.  
Exemplo 1: Problema da Mochila  
Fracionada)  
(
Algoritmo Guloso:  
1
2
3
4
5
6
7
8
9
1
1
1
1
. Mochila_Fracionada(item, valor, peso, n, totalmochila)  
. MergeSort(item, valor, peso, n)  
.
.
.
.
.
.
carga 0  
i 1  
enquanto (carga < totalmochila) e (i <= n) faça  
se (peso[i] totalmochilacarga) então  
pegue todo o item[i]  
carga carga + peso[i]  
. senão  
0.  
1.  
pegue (totalmochila - carga)/peso[i] do item[i]  
carga carga + (totalmochila - carga)/peso[i]  
2. i i + 1  
3. retorne itens pegados  
O(n log n)  
Exemplo 2: Seleção de Atividades  
Seja:  
S = {a1, ... , an): conjunto de n atividades que podem ser executadas em  
um mesmo local. Exemplo: palestras em um auditório.  
Para todo i = 1, ..., n, a atividade ai começa no instante si e termina no  
instante fi, com 0 < si < fi <.  
As atividades ai e aj são ditas compatíveis se os intervalos [si,fi] e [sj, fj]  
são disjuntos.  
Problema: Encontre em S um subconjunto de atividades  
mutuamente compatíveis que tenha tamanho máximo.  
Exemplo 2: Seleção de Atividades  
Exemplo:  
i
1
1
4
2
3
5
3
0
6
4
5
7
5
3
8
6
5
9
7
8
9
10 11  
12  
si  
fi  
6
8
8
2
10 11 12 13 14  
Pares de atividades incompatíveis: (a1, a2), (a1, a3)  
Pares de atividades compatíveis: (a1, a4), (a4, a8)  
Conjuntos máximos de atividades compatíveis:  
(a1, a4, a8, a11) e (a2, a4, a9, a11)  
Exemplo 2: Seleção de Atividades  
Algoritmo Guloso:  
1
2
3
4
5
6
7
8
9
. Seleciona_Atividade(a, s, f, n)  
. MergeSort(a, s, f, n) //ordenação crescente por fi  
. A {a1}  
. i = 1  
. Para m ← 2 até n faça  
. se sm fi então  
.
A ← A {am}  
i m  
.
O(n log n)  
. retorne A  
Método Guloso  
Outros algoritmos gulosos que veremos ao longo do  
curso:  
Algoritmo de Prim (Árvores Geradoras Mínimas)  
Algoritmo de Kruskal (Árvores Geradoras Mínimas)  
Algoritmo de Dijkstra (Distâncias Mínimas)  
Comentários sobre o Método Guloso  
Vantagens:  
Algoritmos simples;  
Fácil implementação;  
Quando garantem soluções ótimas, geralmente são os algoritmos mais  
simples e eficientes;  
Desvantagens:  
Nem sempre garantem soluções ótimas locais;  
Podem efetuar cálculos repetitivos;  
Escolhe o caminho que, à primeira vista, é mais econômico;  
Exercícios  
Lista de Exercícios 04 Método Guloso  
http://www.inf.puc-rio.br/~elima/paa/  
Leitura Complementar  
Levitin. Introduction to the Design and  
Analysis of Algorithms, 3rd Edition, 2011.  
Capítulo 9: Greedy Technique