Análise e Síntese de Algoritmos
Algoritmos Greedy
CLRS, Cap. 16
Resumo
• Algoritmos Greedy:
– Um primeiro exemplo
• Problema de Selecção de Actividades
– Características das abordagens greedy
– Exemplo: Problema da Mochila
– Exemplo: Minimizar Tempo no Sistema
– Um exemplo final: Códigos de Huffman
2003/2004
Análise e Síntese de Algoritmos
2
Técnicas para Síntese de Algoritmos
• Dividir para conquistar
• Programação dinâmica
• Algoritmos greedy
– Estratégia: a cada passo da execução do algoritmo escolher
opção que localmente se afigura como a melhor para
encontrar solução óptima
• Estratégia permite obter solução óptima?
– Exemplos:
• Kruskal, Prim, Dijkstra, etc.
2003/2004
Análise e Síntese de Algoritmos
3
Exemplo: Selecção de Actividades
• Seja S = { 1, 2, …, n } um conjunto de actividades
que pretendem utilizar um dado recurso
– Apenas uma actividade pode utilizar recurso de cada vez
– Actividade i:
• tempo de início: si
• tempo de fim: ti
• execução da actividade durante [si, ti)
– Actividades i e j compatíveis apenas se [si, ti) e [sj, tj) não se
intersectam
• Objectivo: encontrar conjunto máximo de actividades
mutuamente compatíveis
2003/2004
Análise e Síntese de Algoritmos
4
Exemplo (Cont.)
• Admitir que f1  f2  …  fn
• Escolha greedy:
– Escolher actividade com o menor tempo de fim
• Porquê?
– Maximizar espaço para restantes actividades serem realizadas
2003/2004
function Selecionar_Actividades_Greedy(s,f)
n = length[s]
A={1}
j=1
for i = 2 to n
if si  fj then
A=A{i}
j=i
return A
Análise e Síntese de Algoritmos
5
Exemplo (Cont.)
• Algoritmo encontra soluções de tamanho máximo para
o problema de selecção de actividades
– Existe uma solução óptima que começa com escolha greedy,
i.e. actividade 1
• A: solução óptima que começa em k
• B=A-{k}{1}
• f1  fk
– Actividades em B são mutuamente disjuntas e A = B
– B é também solução óptima !
2003/2004
Análise e Síntese de Algoritmos
6
Exemplo (cont.)
– Após escolha greedy, problema reduz-se a encontrar
solução para actividades compatíveis com actividade 1
• Seja A solução óptima, e que começa em 1
• A’ = A - { 1 } é solução óptima para S’ = { i  S : si  f1 }
– Caso contrário, existiria uma solução B’ > A’ para S’ que
permitiria obter solução B para S com mais actvidades do
que A; uma contradição !
– Aplicar indução no número de escolhas greedy
• Algoritmo calcula solução óptima !
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
7
Características das Abordagens Greedy
• Propriedade da escolha greedy
– Óptimo (global) para o problema pode ser encontrado
realizando escolhas locais óptimas
• Sub-estrutura óptima
– Solução óptima do problema engloba soluções óptimas para
sub-problemas
2003/2004
Análise e Síntese de Algoritmos
8
Outro Exemplo: Problema da Mochila
• Definição do problema:
–
–
–
–
–
Dados n objectos (1, …, n) e uma mochila
Cada objecto tem um valor vi e um peso wi
É possível transportar fracção xi do objecto: 0  xi  1
Peso transportado pela mochila não pode exceder W
Objectivo:
• maximizar o valor transportado pela mochila e respeitar
a restrição de peso
• Formalização:
n
max
 xivi
i 1
n
s.t.
 xiw i  W
i 1
v i  0, w i  0, 0  x i  1, 1  i  n
2003/2004
Análise e Síntese de Algoritmos
9
Exemplo (Cont.)
• Observações:
– Soma do peso dos n objectos deve exceder peso limite W
– Solução óptima tem que encher mochila completamente,
 xi w i  W
• Caso contrário poderiamos transportar mais fracções,
com mais valor !
• Algoritmo:
Tempo de
execução:
O(n), ou O(n lg n)
2003/2004
function Encher_Mochila_Greedy(v,w,W)
while weight < W
escolher elemento i com vi/wi máximo
if wi + weight  W then
xi = 1; weight += wi
else
xi = (W-weight)/ wi; weight = W
Análise e Síntese de Algoritmos
10
Exemplo (Cont.)
• Se objectos forem escolhidos por ordem decrescente
de vi/wi, então algoritmo encontra solução óptima
–
–
–
–
Admitir: v1/w1  …  vn/wn
X = (x1, …, xn): solução calculada por algoritmo greedy
Se xi = 1 para todo o i, solução é necessariamente óptima
Caso contrário, seja j menor indíce tal que xj < 1
• Nota:
–
–
–
–
2003/2004
xi = 1, i < j
xi = 0, i > j
Relação de pesos:
Valor da solução é:
ni1 x i w i  W
i1 x i v i  VX
n
Análise e Síntese de Algoritmos
11
Exemplo (Cont.)
– Y = (y1, …, yn): uma qualquer solução possível
n
• Peso:
i1 y i w i  W
n
• Valor:
V Y    y i v i
i 1
– Relação X vs. Y:
i1x i  y i w i  0
n
– Notar que, VX  VY   i1x i  y i v i  i1x i  y i w i
n
n
vi
wi
– Seja j menor indíce tal que xj < 1. Casos possíveis:
• i < j, xi = 1, xi - yi  0, enquanto vi/wi  vj/wj
Verifica-se
• i > j, xi = 0, xi - yi  0, enquanto vi/wi  vj/wj
sempre:
• i = j, vi/wi = vj/wj
xi  yi v i w i   xi  yi v j w j 
2003/2004
Análise e Síntese de Algoritmos
12
Exemplo (Cont.)
– Verifica-se,
V X  V Y   i1 x i  y i w i v i w i   v j w j i1 x i  y i w i  0
n
n
– V(X) é a melhor solução possível entre todas as soluções
possíveis
• Algoritmo calcula solução óptima !
2003/2004
Análise e Síntese de Algoritmos
13
Exemplo: Minimizar Tempo no Sistema
• Dado um servidor com n clientes, com tempo de
serviço conhecido (i.e. cliente i leva tempo ti),
objectivo é minimizar tempo total dispendido no
sistema (pelo total dos n clientes)
min imizar T  i1 tempo total dispendido no sistema pelo cliente i
n
• Exemplo
• Solução (greedy):
– Servir clientes por ordem crescente do tempo de serviço
2003/2004
Análise e Síntese de Algoritmos
14
Exemplo (Cont.)
• Algoritmo greedy encontra solução óptima
– P = p1p2…pn, permutação dos inteiros de 1 a n
• Seja si  t pi
– E.g. s1  t p1  t 5
– Com clientes servidos pela ordem P, tempo de serviço do
cliente a ser servido na posição i é si
– Tempo total passado no sistema por todos os clientes é:
s1 aparece n vezes,
n
TP  k 1 n  k  1sk
e sn aparece 1 vez
– Assumir clientes não ordenados por ordem crescente de
tempo de serviço em P
• Então existem a e b, com a < b, e sa > sb
2003/2004
Análise e Síntese de Algoritmos
15
Exemplo (cont.)
– Trocar ordem dos clientes a e b, de modo a obter ordem P’
• Corresponde a P com inteiros pa e pb trocados
TP'  (n  a  1)sb  n  b  1s a 
n
n  k  1sk

k 1
k  a,b
– Obtendo-se,
TP   TP' 

n  a  1sa  sb   n  b  1sb  sa 
b  a sa  sb   0
– P’ é uma ordem melhor (com menor tempo de serviço)
• Algoritmo calcula solução óptima !
2003/2004
Análise e Síntese de Algoritmos
16
Exemplo: Códigos de Huffman
• Aplicação: compressão de dados
• Exemplo:
– Ficheiro com 100000 caracteres
Frequência
Código Fixo
a
45
000
b
13
001
c
12
010
d
16
011
e
f
9
100
5
101
– Tamanho do ficheiro comprimido: 3x100000 = 300000 bits
– Código de largura variável pode ser melhor do que código com
largura fixa
• Aos caracteres mais frequentes associar códigos de menor
dimensão
2003/2004
Análise e Síntese de Algoritmos
17
Exemplo (Cont.)
• Código de comprimento variável:
Frequência
Código Variável
a
45
0
b
13
101
c
12
100
d
16
111
e
f
9
1101
5
1100
– Número de bits necessário:
• (45*1 + 13*3 + 12*3 + 16*3 + 9*4 + 5*4)*1000 = 224000 bits
• Códigos livres de prefixo:
– Nenhum código é prefixo de outro código
– 001011101

0.0.101.1101
– Código óptimo representado por árvore binária (completa)
2003/2004
Análise e Síntese de Algoritmos
18
Códigos Livres de Prefixo
100
0
Árvore binária completa:
cada nó interno com 2 filhos
1
a:45
55
25
0
c:12
2003/2004
Código óptimo representado
por árvore completa
1
0
30
1
0
b:13
1
14
d:16
0
1
f:5
e:9
Análise e Síntese de Algoritmos
19
Exemplo (Cont.)
• Dada uma árvore T associada a um código livre de
prefixo
– f(c):
– dT(c):
frequência (ocorrências) do caracter c no ficheiro
profundidade da folha c na árvore
BT  
 f c   dT c 
cC
Número de bits
necessário para
representar ficheiro
• Código de Huffman: construir árvore T que corresponde
ao código livre de prefixo óptimo
– Começar com |C| folhas (para cada um dos caracteres do
ficheiro) e realizar |C| - 1 operações de junção para obter árvore
final
2003/2004
Análise e Síntese de Algoritmos
20
Exemplo (Cont.)
function Huffman(C)
n = |C|
Q=C
// Constrói fila de prioridade
for i = 1 to n - 1
z = AllocateNode()
x = left[z] = ExtractMin(Q)
y = right[z] = ExtractMin(Q)
f[z] = f[x] + f[y]
Insert(Q, z)
return ExtractMin(Q)
Tempo de execução: O(n lg n)
2003/2004
Análise e Síntese de Algoritmos
21
Exemplo (Cont.)
• Exemplo
• Código de Huffman para alfabeto C:
– Cada caracter cC com frequência f[c]
– x, y caracteres em C com as menores frequências
– Código óptimo para C representado por árvore binária T
2003/2004
Análise e Síntese de Algoritmos
22
Exemplo (Cont.)
• Facto 1: (propriedade da escolha greedy)
– Existe código livre de prefixo para C tal que os códigos para x e
y (com as menores frequências) têm o mesmo comprimento e
diferem apenas no último bit
• T árvore que representa código óptimo
• b e c caracteres são nós folha de maior profundidade em T
• Admitir, f[b]  f[c], e f[x]  f[y]
• Notar também que, f[x]  f[b], e f[y]  f[c]
• T’: trocar posições de b e x em T
• T’’: trocar posições de c e y em T’
• B(T)  B(T’)  B(T’)  B(T’’)
(*)
• Mas, T é óptimo  B(T’), B(T’’)  B(T)
•  T’’ é uma árvore óptima !
2003/2004
Análise e Síntese de Algoritmos
23
Exemplo (Cont.)
• (*)
BT   BT' 
 f c dT c    f c dT' c 
cC
cC
 f [ x]dT x   f [b]dT b   f [ x]dT ' x   f [b]dT ' b 
 f [ x]dT x   f [b]dT b   f [ x]dT b   f [b]dT x 
 f [b]  f [ x]dT b   dT x 
 0
2003/2004
Análise e Síntese de Algoritmos
24
Exemplo (Cont.)
• Facto 2: (subestrutura óptima)
– Sendo z um nó interno de T, e x e y nós folha
– Considerar um caracter z com f[z] = f[x] + f[y]
– Então T’ = T - {x, y} é óptima para C’ = C - {x, y}  { z }
• B(T) = B(T’) + f[x] + f[y]
(**)
• Se T’ é não óptimo, então existe T’’ tal que B[T’’] < B[T’]
• Mas z é nó folha também em T’’ (devido a facto 1)
– Adicionando x e y como filhos de z em T’’
– Código livre de prefixo para C com custo:
» B[T’’] + f[x] + f[y] < B[T]
– mas T é óptimo (B[T’’] + f[x] + f[y]  B[T]); pelo queT’
também é óptimo
2003/2004
Análise e Síntese de Algoritmos
25
Exemplo (Cont.)
• (**)
f [ x ]dT x   f [ y ]dT y  

2003/2004
f [ x]  f [ y]dT ' z   1
f [ z]dT ' z   f [ x ]  f [ y ]
Análise e Síntese de Algoritmos
26
Exemplo (Cont.)
• O algoritmo Huffman produz um código livre de
prefixo óptimo
– Ver factos anteriores
• Propriedade da escolha greedy
• Sub-estrutura óptima
2003/2004
Análise e Síntese de Algoritmos
27
Revisão
• Algoritmos greedy
– Características das abordagens greedy
– Exemplos de aplicação
• String Matching
2003/2004
(CLRS, Cap. 32)
Análise e Síntese de Algoritmos
28