Análise e Síntese de Algoritmos Algoritmos GreedyCLRS, Cap. 16

Análise e Síntese de Algoritmos

Algoritmos Greedy CLRS, Cap. 16

2003/2004 Análise e Síntese de Algoritmos 2

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


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.


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


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

function Selecionar_Actividades_Greedy(s,f)n = length[s]A = { 1 }j = 1for i = 2 to n

if si fj thenA = A { i } j = i

return A


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 !


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


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


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:

ni1 ,1x0 ,0w ,0v

Wwx.t.s

vxmax

iii

n

1iii

n

1iii


Exemplo (Cont.)

• Observações:– Soma do peso dos n objectos deve exceder peso limite W– Solução óptima tem que encher mochila completamente,

• Caso contrário poderiamos transportar mais fracções, com mais valor !

• Algoritmo:function Encher_Mochila_Greedy(v,w,W)

while weight < Wescolher elemento i com vi/wi máximoif wi + weight W then

xi = 1; weight += wi else

xi = (W-weight)/ wi; weight = W

Wwx ii

Tempo deexecução:O(n), ou O(n lg n)


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:

– xi = 1, i < j

– xi = 0, i > j– Relação de pesos: – Valor da solução é:

n

1i ii Wwx

n1i ii XVvx


Exemplo (Cont.)

– Y = (y1, …, yn): uma qualquer solução possível• Peso:• Valor:

– Relação X vs. Y:

– Notar que,

– Seja j menor indíce tal que xj < 1. Casos possíveis:

• i < j, xi = 1, xi - yi 0, enquanto vi/wi vj/wj

• i > j, xi = 0, xi - yi 0, enquanto vi/wi vj/wj

• i = j, vi/wi = vj/wj

n

1i ii Wwy

n1i iivyYV

0wyx in

1i ii

i

ii

n1i iii

n1i ii w

vwyxvyxYVXV

jjiiiiii wvyxwvyx

Verifica-sesempre:


Exemplo (Cont.)

– Verifica-se,

– V(X) é a melhor solução possível entre todas as soluções possíveis


0wyxwvwvwyxYVXV in

1i iijjiiin

1i ii


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)

• Exemplo

• Solução (greedy):– Servir clientes por ordem crescente do tempo de serviço

n

1i i cliente pelo sistema no dispendido total tempoT imizarmin


Exemplo (Cont.)

• Algoritmo greedy encontra solução óptima – P = p1p2…pn, permutação dos inteiros de 1 a n

• Seja– E.g.

– 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 é:

– 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

ipi ts

kn

1k s1knPT s1 aparece n vezes,

e sn aparece 1 vez

5p1 tts1


Exemplo (cont.)

– Trocar ordem dos clientes a e b, de modo a obter ordem P’• Corresponde a P com inteiros pa e pb trocados

– Obtendo-se,

– P’ é uma ordem melhor (com menor tempo de serviço)


k

n

b,ak1k

ab s1kns1bns)1an('PT

0ssab

ss1bnss1an'PTPT

ba

abba


Exemplo: Códigos de Huffman

• Aplicação: compressão de dados • Exemplo:

– Ficheiro com 100000 caracteres

– 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

a b c d e f Frequência 45 13 12 16 9 5 Código Fixo 000 001 010 011 100 101


Exemplo (Cont.)

• Código de comprimento variável:

– 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)

a b c d e fFrequência 45 13 12 16 9 5Código Variável 0 101 100 111 1101 1100


Códigos Livres de Prefixo

Código óptimo representado por árvore completa

100

55

25 30

14

f:5

a:45

c:12 b:13 d:16

e:9

0

0

0

0

0

1

1

1

1

1

Árvore binária completa:cada nó interno com 2 filhos


Exemplo (Cont.)

• Dada uma árvore T associada a um código livre de prefixo– f(c): frequência (ocorrências) do caracter c no ficheiro– dT(c): profundidade da folha c na árvore

• 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

Cc

T cdcfTBNúmero de bits necessário para representar ficheiro


Exemplo (Cont.)

function Huffman(C)n = |C|Q = C // Constrói fila de prioridadefor 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)


Exemplo (Cont.)

• Exemplo

• Código de Huffman para alfabeto C:– Cada caracter cC 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


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 !


0

xdbd]x[f]b[fxd]b[fbd]x[fbd]b[fxd]x[fbd]b[fxd]x[fbd]b[fxd]x[f

cdcfcdcf'TBTB

TT

TTTT

'T'TTT

Cc'T

CcT

Exemplo (Cont.)

• (*)


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


Exemplo (Cont.)

• (**)

]y[f]x[fzd]z[f

1zd]y[f]x[fyd]y[fxd]x[f

'T

'TTT


Exemplo (Cont.)

• O algoritmo Huffman produz um código livre de prefixo óptimo– Ver factos anteriores

• Propriedade da escolha greedy• Sub-estrutura óptima


Revisão

• Algoritmos greedy– Características das abordagens greedy – Exemplos de aplicação

• String Matching (CLRS, Cap. 32)

Documents

Análise e Síntese de Algoritmos Algoritmos GreedyCLRS, Cap. 16