Método Guloso

Prévia do material em texto

Análise de Algoritmos
MÉTODO GULOSOMÉTODO GULOSO
Bacharelado em Ciência da Computação
Flávia Coelho
flaviacoelho@ufersa.edu.br
Atualizado em Novembro de 2015
 
Sumário
● Motivação
● Exemplo de Utilização
● Elementos Fundamentais
● Leitura Recomendada
 
Motivação
● Para vários problemas de otimização, 
descobrir as melhores escolhas pode ser 
um exagero
● Podemos utilizar algoritmos mais simples e 
eficientes
● Um algoritmo guloso faz uma escolha 
ótima para as condições locais, visando 
uma solução ótima global
 
Por que Guloso?
● Os algoritmos baseados no Método Guloso 
escolhem, a cada passo, o candidato mais 
evidente que possa ser adicionado à solução
● Decisões são tomadas de forma isolada, a 
cada passo
● Estratégia   → escolher o melhor, no momento
 
SOLUÇÃO ÓTIMA LOCAL
 
Exemplo
Escalonamento de Tarefas
● Descrição: Seja T um conjunto de n 
tarefas. Associamos a cada tarefa, um 
tempo de execução e realizamos o 
escalonamento de tarefas
● Problema: Minimizar o tempo médio de 
execução das tarefas
● Sequência de decisões: escolher primeira 
tarefa, escolher segunda tarefa, ... 
 
Exemplo
Escalonamento de Tarefas
● Seja T = {(T1,15), (T2,8), (T3,3), (T4,10)}
● Considerar um único processador e alocação 
não preemptiva
● Estratégia gulosa 1: ordem de chegada
● Estratégia gulosa 2: ordem crescente de 
tempo de execução
 
Sumário
● Motivação
● Exemplo de Utilização
● Elementos Fundamentais
● Leitura Recomendada
 
Exemplo 
Árvores Espalhadas Mínimas
● Árvore é um grafo não­direcionado, conexo 
e acíclico
● Propriedades relevantes de grafos/árvores
● Qualquer grafo não­direcionado, conexo, G = 
(V,A) com |A| = |V| – 1 é uma árvore
● Um grafo não­direcionado é uma árvore se e 
somente se existe um único caminho entre 
qualquer par de nós
 
Formalização do Problema
● Entrada: grafo não­direcionado G = (V, A), 
com pesos de arestas wa
● Saída: árvore T = (V, A'), onde A' ⊆ A que 
minimiza 
● peso(T) = ∑wa, onde a ∈ A' 
 
Exemplo de Instância do Problema
B
1
4
4
3 4
2 4
6
5
A C E
FD
 
Aplicando o Método Guloso
● O algoritmo de Kruskal inicia com um 
grafo vazio e seleciona arestas de A de 
acordo com a regra
● Repetidamente, selecione a próxima aresta 
mais leve que não produz um ciclo
● A árvore é construída aresta por aresta   →
escolhendo sempre a aresta mais barata 
no momento!
 
Tempo de Execução do Algoritmo 
de Kruskal
KRUSKAL (G, w)
Entrada: Grafo não­direcionado conexo com pesos de arestas wa
Saída: Árvore espalhada mínima definida pelas arestas T
para cada vértice v ∈  V   O(V)→
  faça construirConjunto(v) //Cria conjunto contendo apenas v
T = { }    O(1)→
ordenar as arestas de A por peso crescente   O(AlgA)→
para cada aresta (u,v)   A∈ , em ordem de peso crescente   O(A)→
  faça se encontrar(u) != encontrar(v) //a qual conjunto u 
pertence? 
    entao T = T   ⋃ {(u,v)} //adiciona aresta à arvore
      unir(u,v) //une os conjuntos contendo u e v
return T
 
Usando o Algoritmo de Kruskal
● Começamos com um grafo vazio e 
tentamos adicionar arestas em ordem 
crescente de peso (empates são 
decididos arbitrariamente)
B
6
5
2
4 1
2
3
4
4
A C E
FD
5
 
Usando o Algoritmo de Kruskal
B
6
5
2
4 1
2
3
4
4
A C E
FD
5
● Vamos iniciar por B
 
Usando o Algoritmo de Kruskal
● B­C é escolhida
B
6
5
2
4 1
2
3
4
4
A C E
FD
5
B
1
C
→ 
 
Usando o Algoritmo de Kruskal
● Consideramos C
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
 
Usando o Algoritmo de Kruskal
● C­D é escolhida
→ 
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
B
1
C
D
2
 
Usando o Algoritmo de Kruskal
● Consideramos B­D
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
B-D é descartado, pois 
produziria um ciclo
 
Usando o Algoritmo de Kruskal
● Consideramos C­F
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
 
Usando o Algoritmo de Kruskal
● C­F é escolhida
→ 
B
1
C
D
2
F
3
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
 
Usando o Algoritmo de Kruskal
● Consideramos F
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
 
Usando o Algoritmo de Kruskal
● E­F é escolhida
→ 
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
B
1
C
D
2
F
3
E
4
 
Usando o Algoritmo de Kruskal
● Consideramos D­F
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
D-F é descartado, pois 
produziria um ciclo
 
Usando o Algoritmo de Kruskal
● Consideramos A
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
 
Usando o Algoritmo de Kruskal
● A­D é escolhida
B
6
5
4 1
2
3
4
A
FD
5
C E
→ 
B
1
C
D
2
F
3
E
4
A
4
 
Usando o Algoritmo de Kruskal
● Consideramos A­B
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
A-B é descartada, pois 
produziria um ciclo
 
Usando o Algoritmo de Kruskal
● Consideramos C­E
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
C-E é descartada, pois 
produziria um ciclo
 
Usando o Algoritmo de Kruskal
● Consideramos A­C
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
A-C é descartada, pois 
produziria um ciclo
 
Usando o Algoritmo de Kruskal
● Resultado: árvore espalhada mínima, de 
custo 14
→ 
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
B
1
C
D
2
F
3
E
4
A
4
 
Sumário
● Motivação
● Exemplo de Utilização
● Elementos Fundamentais
● Leitura Recomendada
 
Elementos Fundamentais
● Propriedades exibidas pela maioria dos 
problemas aos quais podemos empregar 
o MG
● Escolha gulosa: Uma solução ótima global 
pode ser obtida a partir de escolhas ótimas 
locais (gulosas)
● Subestrutura ótima: Uma solução ótima 
contém em si, soluções ótimas para os 
subproblemas
 
Consequências da Escolha Gulosa
● A escolha pode depender das escolhas 
até o momento, mas não depende de 
nenhuma escolha futura ou de soluções 
para subproblemas
● MG faz uma escolha gulosa após outra, 
reduzindo de modo iterativo cada instância 
do problema para um problema menor
● Frequentemente, a escolha gulosa fornece 
alguma eficiência
 
Programação Dinâmica x Método 
Guloso
● PD particiona o problema em subproblemas 
dependentes (subproblemas compartilham 
subproblemas), resolvendo cada subproblema 
apenas uma vez e armazenando as soluções em uma 
estrutura de dados, para resolver o problema original
● Bottom­up
● MG obtém uma solução para um problema fazendo 
uma sequência de escolhas independentes (para 
cada decisão, a melhor opção é escolhida) para obter 
apenas um subproblema a resolver
● Top­down
 
Programação Dinâmica x Método 
Guloso
● Há sutilezas advindas do uso de 
subestrutura ótima
● Vamos considerar 2 variantes do 
problema da mochila
● Problema da mochila 0­1 (binária)
● Problema da mochila fracionária
 
Exemplo
Problema da Mochila
● Um ladrão que rouba uma loja encontra n itens: o 
i­ésimo item vale vi reais e pesa wi kg, onde vi e wi 
são inteiros
● Ele deseja levar uma carga o mais valiosa 
possível, mas pode carregar no máximo W kg em 
sua mochila
● Que itens ele deve levar?
● Mochila 0­1 (binária), em que cada item deve ser 
levado ou deixado (o ladrão não pode levar frações)
● MochilaFracionária, em que o ladrão pode levar 
frações de itens
 
Exemplo
Problema da Mochila
● Ambas as modalidades exibem a 
propriedade de subestrutura ótima
● Para o 0­1, considere a carga mais valiosa que pesa W 
kg, se removermos o item j, a carga restante deve ser a 
carga mais valiosa que pese, no máximo, W – wj que o 
ladrão pode levar dos n­1 itens originais (excluindo j)
● Para o fracionário, se removermos um peso w de um 
item j da carga ótima, a carga restante deve ser a carga 
mais valiosa que pese no máximo W – w que o ladrão 
pode levar dos n­1 itens originais, mais wj – w que os 
do item j
 
Mochila Fracionária com MG
● Primeiro, calculamos o valor por quilo (vi/wi) 
para cada item
● O ladrão começa levando o máximo possível 
do item com o maior valor por quilo
● Se o suprimento do item acabar, e se ele 
ainda puder levar mais, o ladrão poderá 
levar tanto quanto possível do item com o 
próximo maior valor por quilo até não poder 
levar mais nada
● Tempo de execução é O(nlgn)
 
Mochila Fracionária com MG
● Vejamos uma instância do problema
● 3 itens e a mochila pode conter até 50kg
10
20
30Item 1
Item 2
Item 3
$60 $100 $120
50
Mochila
Valor/kg: $6
Valor/kg: $5
Valor/kg: $4
 
Resultado da Mochila Fracionária
● Tomar os itens em ordem de maior valor 
por quilo produz uma solução ótima
● Com base em 'levar o' item 1 primeiro!
50
$80
+
$100
+
$60
= $24010
20
20
/
30
Estratégia gulosa: Maximizar o 
lucro a cada passo
 
Mochila Binária com PD
● A solução ótima leva os itens 2 e 3, 
deixando o item 1 para trás
● As 2 soluções que envolvem o item 1 não 
são ótimas
$120
+
$100
= $220
50
20
30
50 50
$100
+
$60
= $160
10
20
10
30
$120
+
$60
= $180
 
Mochila Binária com PD
● Na modalidade 0­1, quando consideramos 
um item para inclusão na mochila, devemos 
comparar a solução para o subproblema no 
qual o item é incluído com a solução para o 
subproblema no qual o item é excluído, 
antes de fazer a escolha
● Geram­se muitos subproblemas superpostos
● Caso legítimo de aplicação da PD!!!
 
Aplicabilidade do MG
● Códigos para transmissão de mensagens 
(Código de Huffman)
● Escalonamento de tarefas
● Caminhos de custo mínimo em grafos
 
Referências
Material didático elaborado por Jorge Cesar 
Abrantes de Figueiredo, UFCG 
(Universidade Federal de Campina 
Grande)
 
Leitura Recomendada
S. Dasguta, C. Papadimitriou, U. Vazirani. 
Algoritmos. Mc­Graw Hill, 2009, pp. 127­
147
T. H. Cormen, C. E. Leiserson, R. L. Rivest, 
C. Stein. Algoritmos. Teoria e Prática. 
Tradução da Segunda Edição Americana. 
Campus, 2002, pp. 303­307
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44