Aula 8 - Algoritmos Gulosos

Prévia do material em texto

Algoritmos Gulosos
Prof. Ricardo P. Mesquita
Algoritmos Gulosos
A estratégia gulosa é útil principalmente para resolver problemas de otimização 
combinatória, cujas soluções possam ser alcançadas por sequências de decisões. 
Essa estratégia pode ser aplicada a problemas de otimização combinatória, como 
por exemplo:
 intercalação sucessiva ótima de listas; 
 caminhos de custo mínimo em grafos orientados;
 árvore geradora (ou de espalhamento) mínima em grafos não orientados; 
 códigos para transmissão de mensagens (códigos de Huffman); 
 escalonamento de tarefas.
02/29Prof. Ricardo Mesquita
Estratégia Gulosa 
 Exemplo: intercalação sucessiva de listas
 Trata-se de intercalar n listas. 
 Há várias maneiras possíveis de se realizar uma sequência de intercalações. 
 Ocorre que isso pode afetar o número de comparações necessárias. Por exemplo:
 Seja intercalar duas listas m1 e m2. O comprimento da lista resultante será m1 + m2. Número de 
comparações, no pior caso m1 + m2 – 1.
 Seja intercalar três listas m1, m2 e m3 com comprimentos 15, 10 e 5.
 Intercalar m1 e m2 (15 + 10 – 1 = 24 comparações), e depois, o resultado com m3 (15 + 10 + 5 – 1 = 29 
comparações), totalizando 24 + 29 = 53 comparações.
 Outra maneira, seria Intercalar m2 e m3 (10 + 5 – 1 = 14 comparações). E depois, o resultado com m1
(15 + 10 + 5 – 1 = 29 comparações), totalizando 14 + 29 = 43 comparações.
Prof. Ricardo Mesquita
Neste caso, o objetivo é encontrar a melhor sequência para comparar as listas.
03/29
Estratégia Gulosa 
 Exemplo: intercalação sucessiva de listas
 Estratégia: os primeiros pares a serem intercalados dão maior contribuição para o 
peso total.
 Exemplo: intercalar 5 listas, de comprimento 10, 20, 30, 40 e 50, respectivamente. Com 
quantas comparações podemos intercalar essas listas?
04/29Prof. Ricardo Mesquita
Estratégia Gulosa 
 Algoritmo para intercalação ótima de listas
05/29Prof. Ricardo Mesquita
Estratégia Gulosa
 Ideias básicas:
 Útil em problemas de otimização cuja solução pode ser alcançada por uma sequência de 
decisões
 Princípio importante: construir por etapas uma resposta ótima
 Em cada passo, após selecionar um elemento da entrada (o melhor), decide-se se ele é viável –
vindo a fazer parte da resposta – ou não. 
 Após uma sequência de decisões, uma solução para o problema é alcançada. 
 Nessa sequência de decisões, nenhum elemento é examinado mais de uma vez: ou ele fará 
parte da saída, ou será descartado. 
 Frequentemente, a entrada do problema já vem classificada.
06/29Prof. Ricardo Mesquita
Estratégia Gulosa
 A ideia básica da estratégia gulosa sugere uma estrutura geral para algoritmos 
gulosos: uma sequência, consistindo em um trecho de inicialização seguido de uma 
iteração e um trecho de finalização. 
 Assim, um algoritmo guloso tem a forma: inicialização > iteração > finalização
07/29Prof. Ricardo Mesquita
Estratégia Gulosa
Os passos...
 A inicialização prepara a entrada (muitas vezes a entrada é classificada) e 
inicializa a saída.
 a iteração seleciona um elemento conforme uma função gulosa, marca-o para 
não considerá-lo novamente no futuro, atualiza a entrada, examina o elemento 
selecionado quanto sua viabilidade e decide sobre a sua participação ou não 
na solução. 
 A finalização recupera a saída.
08/29Prof. Ricardo Mesquita
Projeto de Algoritmos pela Estratégia Gulosa
 Vamos examinar o problema de caminhos de custo mínimo em grafo orientado a 
partir de uma fonte. 
 O problema consiste em determinar um caminho de custo mínimo a partir de um 
vértice fonte a cada vértice do grafo. 
 Uma estratégia gulosa para determinar caminhos de custo mínimo a partir de um 
vértice fonte usa um conjunto de vértices intermediários, que é incrementado em 
cada passo. 
09/29Prof. Ricardo Mesquita
Projeto de Algoritmos pela Estratégia Gulosa
 Exemplo: Caminhos de custo mínimo a partir de fonte em grafo Consideremos
grafo orientado G = <V, E > abaixo
10/29Prof. Ricardo Mesquita
Projeto de Algoritmos pela Estratégia Gulosa
 O grafo G tem 5 vértices V = {a, b, c, d, e} e 6 arestas com a seguinte matriz de 
custos:
11/29Prof. Ricardo Mesquita
Projeto de Algoritmos pela Estratégia Gulosa
 Consideremos como fonte o vértice a. 
 Uma estratégia gulosa razoável se baseia em um conjunto I de vértices a serem 
usados como intermediários nos caminhos. 
 Inicialmente, o conjunto I de vértices intermediários é vazio, e o vetor de distâncias é 
a primeira linha da matriz de custos anterior, ou seja:
12/29Prof. Ricardo Mesquita
Projeto de Algoritmos pela Estratégia Gulosa
 Em cada passo, seleciona-se como novo intermediário um vértice que tenha distância 
mínima e são atualizadas as distâncias. 
 No passo 1, o vértice selecionado como novo intermediário é b. 
 Com isso obtemos novos caminhos a partir de a passando por b: até c com 
comprimento 3 + 3 = 6 < ∞ e, até d com comprimento 3 + 2 = 5 < ∞ e até e com 
comprimento 3 + 7 = 10 < 11. 
 Desse modo, obtém-se a seguinte sequência de passos.
13/29Prof. Ricardo Mesquita
Projeto de Algoritmos pela Estratégia Gulosa
 Após o passo 4, teremos I = {b, c, d, e}, sendo o custo mínimo de caminhos da fonte 
a cada vértice alcançável dados pela última linha, ou seja:
 Essa tabela fornece o custo mínimo de caminhos da fonte a cada vértice alcançável.
14/29Prof. Ricardo Mesquita
Projeto de Algoritmos pela Estratégia Gulosa
15/29Prof. Ricardo Mesquita
Exemplo:
9
D
A
E
B
C
F3
4
8
4
7
2
2
5
9
árvore geradora
peso = 15
D
A B
C
E F
árvore geradora
peso = 24
D
A
E
B
C
F
3
4
8
4 5
3
4
4
2
2
Exemplo: Árvore Geradora Mínima
Prof. Ricardo Mesquita 16/29
Algoritmo de Kruskal
 Princípio: a aresta de menor peso sempre pertence à árvore geradora de peso 
mínimo.
 Prova
 Suponha que a aresta de peso mínimo não pertença à solução ótima.
 Inserindo-se a aresta de peso mínimo nesta solução ótima, obtém-se um ciclo.
 Pode-se obter uma nova árvore geradora removendo-se a aresta de maior peso.
 Esta nova árvore geradora teria peso menor do que a anterior, portanto aquela 
solução não poderia ser ótima.
Prof. Ricardo Mesquita 17/29
Algoritmo de Kruskal
Criar uma lista L com as arestas ordenadas em ordem 
crescente de pesos.
Criar |V| subárvores contendo cada uma um nó isolado.
F  
contador  0
Enquanto contador < |V|-1 e L   faça
Seja (u,v) o próximo arco de L.
L  L – {(u,v)}
Se u e v não estão na mesma subárvore então
F  F  {(u,v)}
Unir as subárvores que contêm u e v.
contador  contador + 1
fim-se
fim-enquanto
Prof. Ricardo Mesquita 18/29
Exemplo:
83
9
D
A
E
B
C
F
4
4
7
2
2
5
9
e c(e)
(C,F) 2
(E,F) 2
(A,D) 3
(C,E) 3
(A,B) 4
(A,E) 4
(B,F) 5
(D,F) 7
(B,C) 8
(B,E) 9
(C,D) 9
Lista L
Subárvores
{ A } { B } { C } { D } { E } { F }{ A } { B } { C, F } { D } { E }
c(F) = 2
{ A } { B } { C, E, F } { D }
c(F) = 4
{ A, D } { B } { C, E, F }
c(F) = 7
{ A, B, D } { C, E, F }
c(F) = 11
{ A, B, C, D, E, F }
c(F) = 15
3
X
Algoritmo de Kruskal
Prof. Ricardo Mesquita 19/29
Exemplo:
H
A
B
J
C
e c(e)
(D,E) 1
(D,L) 2
(F,J) 2
(G,J) 2
(C,D) 3
(E,F) 3
(H,I) 3
(A,B) 4
(B,C) 4
… …
Lista L
Subárvores
c(F) = 1
E
M L
G
D
I
F
4
7
4
3
7
5
6
2
2
3
1
4
2
3
8
6
4
{ A } { B } { C } { D } { E } { F }
{ G } { H } { I } { J } { L } { M }
{ A } { B } { C } { D, E } { F }
{ G } { H } { I } { J } { L } { M }
c(F) = 3
{ A } { B } { C } { D, E, L } { F }
{ G } { H } { I } { J } { M }
{ A } { B } { C } { D, E, L }
{ F, J } { G } { H } { I } { M }
c(F) = 5
{ A } { B } { C } { D, E, L }
{ F, G, J } { H } { I } { M }
c(F) = 7
{ A } { B } { C, D, E, L }
{ F, G, J } { H } { I } { M }
c(F) = 10
{ A } { B } { C, D, E, L, F, G, J }
{ H } { I } { M }
c(F) = 13
{ A } { B } { C, D, E, L, F, G, J }
{ H, I } { M }
c(F) = 16
{ A, B } { C, D, E, L, F, G, J }
{ H, I } { M }
c(F) = 20
{ A, B,C, D, E, F, G, J, L }
{ H, I } { M }
c(F) = 24
Algoritmo de Kruskal
Prof. Ricardo Mesquita 20/29
Exemplo:
H
A
B
J
C
Lista L
Subárvores
E
M L
G
D
I
F
4
7
4
3
7
5
6
2
2
3
1
4
2
3
8
6
4
{ A, B, C, D, E, F, G, J, L }
{ H, I } { M }
c(F) = 24
e c(e)
... ...
(A,I) 4
(J,L) 4
(G,M) 5
(C,M) 6
(I,J) 6
(A,M) 7
(G,H) 7
(B,L) 8
{ A, B, C, D, E, F, G, H, I, J, L }
{ M }
c(F) = 28
X
{ A, B, C, D, E, F, G, H, I, J, L, M }
c(F) = 33
Algoritmo de Kruskal
Prof. Ricardo Mesquita 21/29
Complexidade de Algoritmos Gulosos
 Vamos examinar o algoritmo que calcula os caminhos a partir de uma fonte 
(visto anteriormente):
Prof. Ricardo Mesquita 22/29
Complexidade de Algoritmos Gulosos
 O para da linha 2 leva a n iterações. Assim, a complexidade da inicialização (linhas 0, 
1 e 2) tem ordem O(n).
 A complexidade da linha 4 é o tamanho de p, que começa com n = | V0 | e diminui de 
1 a cada iteração. 
 O para das linhas de 3 a 10 faz n iterações. 
 O trecho das linhas 4 e 5 tem complexidade | p | = n − i e o para das linhas de 6 a 9 
faz n iterações. 
 Assim, o corpo da iteração (linhas de 4 a 9) tem complexidade | p | + n = (n − i) + n, 
que varia durante a iteração. 
Prof. Ricardo Mesquita 23/29
Complexidade de Algoritmos Gulosos
 Desse modo, a complexidade da iteração é dada pelo somatório
 Assim, a complexidade da iteração tem ordem Ο(n2). 
 A complexidade da linha 11 é Ο(n). 
 Portanto, a complexidade do algoritmo tem ordem 
cP[ a ](n) = Ο(n + n
2 + n) = Ο(n2).
Prof. Ricardo Mesquita 24/29
Complexidade de Algoritmos Gulosos
 Vamos analisar com mais detalhe:
 Assim, desemp[ linhas 4-5 ](pi, disti) ≤ (n − i + 1) + (n − i + 1) ≤ 2(n + 1).
Prof. Ricardo Mesquita 25/29
Complexidade de Algoritmos Gulosos
 Assim, como na i-ésima iteração, as linhas 7 e 8 são executadas com n = | V0 | vezes, 
temos desemp[ linhas 6-9 ](pi+1, disti) ≤ 2n.
 Desse modo, uma cota superior para o desempenho do corpo na i-ésima iteração é 
dado pela soma das cotas para as contribuições:
Prof. Ricardo Mesquita 26/29
Complexidade de Algoritmos Gulosos
 Agora, como a iteração (linhas de 3 a 10) repete n vezes, uma cota superior para o 
desempenho da iteração é
n(4n + 2)= 4n2 + 2n
 Ou seja, desemp[ Iter ]  4n2 + 2n.
 O desempenho da finalização tem a seguinte contribuição:
Prof. Ricardo Mesquita 27/29
Complexidade de Algoritmos Gulosos
 Desempenho do algoritmo:
 Ou seja, cP[Dist_fnt ](n) = Ο(n
2).
Prof. Ricardo Mesquita 28/29
Dúvidas?
Prof. Ricardo Mesquita 29/29