Algoritmos Guloso para Otimização Combinatória

Prévia do material em texto

Algoritmos –APA5 - Algoritmos Gulosos - Alexandre Andreatta - 20081 1 
ALGORITMOS GULOSOS 
 
Algoritmos para problemas de otimização combinatória tipicamente percorrem uma 
seqüência de passos para construir/obter uma solução ótima. Depois de cada passo há um 
conjunto de alternativas para o próximo passo. Um algoritmo guloso sempre faz uma 
escolha que parece ser a melhor no momento. Faz uma escolha ótima localmente, na 
esperança que esta escolha leve à uma solução ótima globalmente. 
 
A Estratégia Gulosa têm muita similaridade com Programação Dinâmica, pois ambas 
exigem que o problema tratado tenha sub-estrutura ótima. Uma diferença fundamental 
entre as duas estratégias é que nos algoritmos gulosos a propriedade de sub-estrutura ótima 
é utilizada de forma top-down. Isto significa que em vez de obter primeiramente soluções 
ótimas para subproblemas e fazer as escolhas dos subproblemas que compõe a solução 
final, algoritmos gulosos primeiro fazem a escolha que se mostra melhor correntemente, e 
depois resolvem o subproblema resultante. 
 
1 – Construção de um Algoritmo baseado na Estratégia Gulosa 
 
A construção de um algoritmo que utiliza a Estratégia Gulosa na solução de um problema 
de otimização combinatória obedece, geralmente, os seguintes passos: 
 
1. Determinar a sub-estrutura ótima do problema. 
2. Modelar o problema como uma recursão. 
3. Provar que em qualquer etapa da recursão, uma das escolhas que levam a uma solução 
ótima é a escolha gulosa. 
4. Mostrar que só há um único subproblema a ser resolvido depois da escolha gulosa. 
5. Construir um algoritmo recursivo que implementa a estratégia gulosa. 
6. Converter o algoritmo recursivo num algoritmo iterativo ou utilizar memorização 
 
De forma mais sucinta, a construção do Algoritmo Guloso obedece os seguintes passos: 
 
1. Reduza o problema de otimização a um problema para o qual fazemos uma escolha e 
somos deixados com um único subproblema para resolver. 
2. Prove que sempre há uma solução ótima para o problema original que faz a escolha 
gulosa, mostrando que a escolha gulosa é sempre segura. 
3. Mostre que, tendo feito a escolha gulosa, o que resta é um subproblema com a 
propriedade de que se combinarmos uma solução ótima ao subproblema com a escolha 
gulosa que fizemos, chegamos a uma solução ótima ao problema original. 
 
2 - Problema da Seleção de Atividade (PSA) 
 
Considere um conjunto de n atividades S = { a1 , a2 , ... , an }, cada qual pretendendo 
utilizar um recurso que só pode ser utilizado por uma atividade de cada vez (como uma 
sala de aula para uma disciplina, por exemplo). Cada atividade ai tem um tempo para 
começar si e um tempo para terminar ti,onde si ≤ ti. Se a atividade ai for selecionada, ela 
usará o recurso no intervalo [si,ti.]. 
Algoritmos –APA5 - Algoritmos Gulosos - Alexandre Andreatta - 20081 2 
As atividades ai e aj são compatíveis se sj ≥ ti ou se si ≥ tj . Obtenha um conjunto A ⊆ S de 
atividades mutualmente compatíveis que seja maximal. 
 
algoritmo selecionaGuloso(s[], t[],n) 
ordene s[] e t[] por ordem crescente de t // reordenar as atividades também... 
A ← {1}; j ← 1 
para i = 2 até n faça 
 se ( s[i] ≥ t[j] ) então { A ← A ∪ { i }; j ← i } 
fim-para 
retorne A 
 
Prova da Corretude: selecionaGuloso produz uma solução de tamanho máximo 
Seja S = {1, 2, ..., n} o conjunto de atividades já considerando a ordenação. Neste caso, 
t[1] é o menor tempo de término. Vamos mostrar que existe solução ótima A tal que 1 ∈ A 
 
Seja C ⊆ S uma solução ótima. Suponha que as atividades estejam ordenadas em C. Seja k 
a 1a atividade escolhida na solução C. Então, necessariamente t[1] ≤ t[k]. Portanto, a 
solução A=C-{k}∪{1} é viável e é maximal, pois | A | = | C | 
 
Uma vez que A é uma solução ótima para S, então A1 = A - {1} é uma solução ótima para 
o problema gerado por S1 = { i ∈ S : s[i] ≥ t[1] }. Se fosse possível conseguir uma solução 
B1 com mais atividades do que A1, então seria possível conseguir uma solução B para S 
com mais atividades do que a solução A, o que seria uma contradição. 
 
Então, após a escolha ótima local, resta um sub-problema dado por S1 = { i∈S: s[i] ≥ t[1]}, 
independente da primeira escolha, que deve conter na sua solução aquela atividade j∈ S1 
com o menor tempo t[ ]. Esta mecânica de escolha se propaga ao longo das decisões, 
justificando o uso do algoritmo guloso. 
 
Complexidade de selecionaGuloso 
A ordenação é feita em O(n log n). O loop é realizado n-1 vezes. A inserção da atividade j 
no conjunto A pode ser feita em tempo constante O(1). Portanto, o algoritmo é afetado 
principalmente pela ordenação, e sua complexidade é O(n log n). 
 
3 - Problema da Mochila 
 
Problema Fracionário da Mochila (PFM) 
 
Dado um conjunto S = {1,2,.., n}, onde a cada item i estão associados um peso wi e um 
valor vi, e uma “mochila” com capacidade para um peso W, 
 Maximize ∑
=
×
ni
ii xv
,..,1
 
 Sujeito a ∑
=
≤
ni
ii Wwx
,...,1
 , Sixi ∈∈ ],1,0[ 
Algoritmos –APA5 - Algoritmos Gulosos - Alexandre Andreatta - 20081 3 
O objetivo é obter um valor para x = ( x1, x2 , ... , xn ) que maximize a função dada. Se o i-
ésimo item não é colocado na mochila, xi = 0. 
 
O PFM tem sub-estrutura ótima: Sendo x uma solução ótima, se retirarmos um peso p de 
um item j, xjwj ≥ p, o vetor y = ( x1, x2 , ... , xj-1, (xjwj - p)/wj , xj+1 , ... , xn ) é solução ótima 
para uma restrição W - p com os n itens e com o j-ésimo item tendo peso wj - p. Se 
houvesse uma solução melhor do que y para o sub-problema, seria possível obter uma 
solução melhor do que x para o problema original, adicionando-se p partes de j. Este 
problema admite a estratégia gulosa, inserindo os itens em ordem decrescente de v/w. 
 
algoritmo PFMguloso(n, W, S[ ], x[ ]) // solução em x[ ] 
 Ordene S pelas frações v/w // ordem decrescente 
 k ← 1 ; total ← 0 
 loop 
 se ( total + S[k].w < W ) então x[ k ] ← 1; total ← total + S[k].w 
 senão 
 x[ k ] ← (W – total )/ S[k].w ; saia do loop 
 fim-se 
 k ← k + 1 
 fim-loop 
 para i = k+1 até n faça x[ i ] ← 0; 
 
Problema da Mochila 0-1(PM 0-1) 
 
Dados n itens de um conjunto S = {1,2,.., n}, onde a cada item i estão associados um peso 
wi e um valor vi, e uma mochila com capacidade para um peso W, 
 Maximize ∑
=
×
ni
ii xv
,..,1
 
 Sujeito a ∑
=
≤
ni
ii Wwx
,...,1
, Sixi ∈∈ },1,0{ 
Cada item escolhido é colocado inteiro, não sendo permitido colocar frações de itens. 
 
Se x=( x1, x2 , ... , xn ) é uma solução ótima para o problema e o item j é retirado do 
problema, o vetor y=( x1, x2 , ... , xj-1, xj+1 , ... , xn ) é uma solução ótima para o 
subproblema S’ = S - {j} restrito a W - wj (por que?). Mas um algoritmo guloso não 
fornece, necessariamente uma solução ótima para o problema. Por exemplo: 
Considere W=50, S = {1,2,3}, w = [10, 20,30], v = [60, 100, 120]. O conjunto S já está 
ordenado por v/w = [6, 5, 4] A solução gulosa x1=( 1,1,0) tem valor 160. A solução não-
gulosa x2=( 0,1,1) tem valor 220 é melhor do que x1 e é ótima. 
 
Quando a estratégia gulosa não pode ser aplicada a um problema, o erro de uma solução 
obtida por uma estratégia gulosa pode ser arbitrariamente grande. Por exemplo, no 
problema da Cobertura por Vértices de um grafo G=(V,E), se busca W ⊆ V com o 
menor número de vértices, tal que para todo ( u, v ) ∈ E, u ∈ W ou v ∈ W. Se adotarmos a 
estratégia gulosa (selecionar os vértices de maior grau), nos aproximamos de um erro de 
quase 100% em certos casos: 
Algoritmos –APA5 - Algoritmos Gulosos - Alexandre Andreatta - 20081 4 
 
 
 
 
 
 
 
 
 
 
 
4 –Codificações de Huffman 
 
Os códigos de Huffman são utilizados paracodificar caracteres objetivando maximizar a 
compactação. 
 
Suponha que temos um arquivo com 100.000 caracteres do alfabeto {a,b,c,d,e,f} que 
desejamos compactar. Os caracteres ocorrem com as seguintes freqüências (em milhares): 
 a b c d e f 
Freqüência 45 13 12 16 9 5 
 
Usando uma codificação de tamanho fixo, precisamos de  ln2 n bits para representar n 
caracteres (no exemplo, 2�=8, 6<8). 
 a b c d e f 
Código 000 001 010 011 100 101 
Esta codificação requer 300.000 bits pra armazenar o arquivo dado. 
Uma codificação de tamanho variável pode diminuir este total, usando códigos mais 
curtos para caracteres mais frequentes. 
 a b c d e f 
Código 0 101 100 111 1101 1100 
 
Solução gulosa: 
2n + 2 vértices na 
cobertura a partir dos 
vértices com maior grau 
n + 2 vértices 
n + 2 vértices 
n vértices 
 
n + 2 vértices 
n vértices 
Solução ótima: n + 2 vértices 
na cobertura a partir dos 
vértices indicados
 
Algoritmos –APA5 - Algoritmos Gulosos - Alexandre Andreatta - 20081 5 
Este código requer (45*1 + 13*3 + 12*3 + 16*3 + 9*4 +5*4) *1000=224000 bits para 
representar o arquivo, economizando aproximadamente 25% no espaço de armazenamento 
 
Um código de Huffman é uma codificação otimizada binária, de tamanho variável, e o 
código de cada caracter não é prefixo do código de outro caracter. Logo, não há 
ambigüidade na leitura. 
 
Temos a garantia desta propriedade porque a codificação de Huffman é uma codificação 
prefixa, construída a partir de uma árvore binária. Na construção da codificação, os 
caracteres são as folhas da árvore binária, e as arestas representam as decisões de 
utilização de bits (0 ou 1). Árvores binárias também geram codificações prefixas de 
tamanho fixo. Neste caso, as folhas devem estar todas no mesmo nível. 
 
 
1 0 0 
 
1 0 
 
1 4 
 
 
8 6 
 
 
1 4 
 
 
2 8 
 
 
5 8 
 
 
a (4 5 ) 
 
b (1 3 ) 
 
c (1 2 ) 
 
d (1 6 ) 
 
 
e (9 ) 
 
f (5 ) 
1 1 0 0 
0 1 0 
1 0 
1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 
 
A árvore binária seguinte apresenta uma codificação de Huffman para o mesmo problema. 
 
 
1 00 
 
 
55 
 
 
14 
 
 
2 5 
 
 
3 0 
 
 
a (4 5 ) 
 
b (13 ) 
 
c (12 ) d (16 ) 
 
 e (9 ) 
 
f (5 ) 
1 1 0 
0 
0 
1 
0 
1 0 
1 
0 
1 101 
1 11 10 1 1 00 
1 10 0 
 
Uma codificação de Huffman é sempre apresentada por uma árvore binária onde cada nó 
interno tem exatamente 2 filhos. Se C é o conjunto dos caracteres do texto, então a árvore 
Algoritmos –APA5 - Algoritmos Gulosos - Alexandre Andreatta - 20081 6 
tem exatamente |C| folhas, uma para cada letra do conjunto, e exatamente |C|-1 nós 
internos. A profundidade de uma folha corresponde ao tamanho do seu código. 
O problema, portanto, tem como entrada um conjunto de caracteres c ∈ C, e a freqüência 
de f(c) de cada caractere c, e como saída, uma árvore T que representa o código, e que 
minimiza a soma de f(c)*dT(c), onde dT(c) é a profundidade de c na árvore T. Desta forma 
é gerada uma tabela onde os elementos que aparecem maior número de vezes recebem 
códigos mais curtos, que vão ocupar menos espaço para armazenamento. 
 
O número de bits na compactação do arquivo, custo da árvore T, é ∑
∈
=
C
T )()( B(T)
c
cdcf 
Construindo uma codificação de Huffman 
 
O Problema da Codificação de Huffman pode ser formulado como: 
Obtenha uma árvore binária T que codifique C tal que B(T) seja mínimo 
 
O algoritmo deve construir uma árvore correspondente à codificação otimizada. No 
pseudo-código a seguir, assume-se que C possui n caracteres numerados de 1 a n, índices 
dos caracteres. A freqüência do i-ésimo caractere em C é indicada pelo elemento f[i] de 
uma array. Uma fila de prioridades Q, uma heap binária com valor mais prioritário sendo o 
menor valor de f, é usada pra identificar os dois nós x, y com menores freqüências. Estes 
nós serão filhos de um novo nó interno z, cuja freqüência será a soma f[x]+f[y]. Cada nó 
interno da árvore contém os atributos esquerdo, direito, freqüência. As folhas, caracteres 
originais, são referenciadas por seus índices. O nó interno 1 é a raiz. 
 
Algoritmo Huffman ( in f[ ] , n , out esquerdo[ ] , direito[ ] ) 
tamanho ← n 
buildHeapModificada( Q[ ] , tamanho , f[ ] ) 
// a prioridade é dada por f, a permutação produzida é dos índices dos caracteres 
para z = n-1 até 1 faça 
esquerdo ← ExtraiMin( Q ) ; direito ← ExtraiMin( Q ) 
f[z+n] ← f[esquerdo] + f[direito] ; 
esquerdo[z] ← esquerdo ; direito[z] ← direito 
InsereHeapModificado(Q[ ], tamanho, z + n ) 
fim-para 
 
Complexidade 
 
A inicialização de Q é executada em O(n) utilizando BuildHeap. O loop é executado n -1 
vezes. Cada operação de heap é feita em tempo O(lg n). Portanto, o loop contribui O(n lg 
n) para o tempo de execução. Então, o tempo de execução total de Huffman para n 
caracteres é O(n lg n). 
 
Corretude do algoritmo de Huffman (Imediato pelos lemas 1 e 2) 
 
Algoritmos –APA5 - Algoritmos Gulosos - Alexandre Andreatta - 20081 7 
Lema 1 
Uma árvore ótima pode ser construída começando com a escolha gulosa dos 
caracteres com menores freqüências Em outras palavras, considere x, y ∈ C com as 
menores freqüências. Então existe um código de prefixo otimizado para C em que os 
códigos de x e y tem o mesmo comprimento e se diferem apenas no último bit. 
Prova 
Considere uma árvore T com código de prefixo otimizado. Queremos transformá-la para 
representar outro código, tal que os caracteres x e y fiquem como folhas de máxima profundidade. 
Se isto é possível, então os códigos de x e y terão o mesmo tamanho, só diferenciando-se no 
ultimo bit. 
 
Sejam b e c dois caracteres que são folhas de máxima profundidade em T. Suponha que f(b) ≤ f(c) 
e f(x) ≤ f(y). Já que f(x) e f(y) são as menores freqüências em folhas, e f(b) e f(c) são duas 
freqüências arbitrárias, temos f(x)≤ f(b) e f(y) ≤ f(c). Trocamos as posições de b e x pra produzir 
uma árvore T1. A diferença no custo entre T e T1 é: 
B(T)-B(T1)=∑ ∈Cc f(c)dT(c)-∑ ∈Cc f(c)dT1(c) = f(x)dT(x) + f(b)dT(b) - f(x)dT1(x) - f(b)dT1(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)) 
 
Sabemos que B(T)-B(T1) ≥ 0 pois f(b)-f(x)≥ 0 e dT(b)- dT(x) ≥ 0. Trocando as posições de c e y, 
De forma similar, a troca de y e c em T1 para produzir uma árvore T2 , não aumenta o custo. Então 
B(T1) - B(T2) ≥ 0. Portanto, B(T2) ≤ B(T), e como T é ótima, B(T) ≤ B(T2). Logo, B(T2)=B(T). 
Então, T2 é uma árvore otimizada onde x e y aparecem como folhas de máxima de profundidade 
fim-prova 
 
Lema 2 
Construir codificações de prefixo otimizados tem a propriedade da sub-estrutura 
ótima. Em outras palavras, seja T uma árvore binária de uma codificação prefixa 
otimizada de C, onde f(c) é a freqüência de c∈C. Sejam x e y folhas em T, e seja z o pai. 
Então f(z) = f(x) + f(y), e a árvore T1 =T-{x, y} é uma codificação prefixa otimizada para 
C1 =C - {x,y} ∪ {z}. 
Prova: 
B(T) pode ser expresso em termos de B(T1). Para cada c∈ C - {x,y}, dT(c)= dT1(c), e 
f(c)dT(c)=f(c)dT1(c). Como dT(x)= dT(y)= dT1(z)+1 temos: 
 
f(x)dT(x)+f(y)dT(y)= (f(x)+f(y) )(dT1(z)+1) = ( f(x)+f(y) ).dT1(z) + f(x)+f(y) = f(z) dT1(z)+f(x)+f(y) 
 
Logo, B(T) = B(T1) + f(x) + f(y) 
 
Se T1 representa uma codificação NÃO-otimizada para C1, então deve haver uma árvore T2 cujas 
folhas são caracteres de C1, tal que B(T2)<B(T1). Como z é tratado como caractere em C1, aparece 
como uma folha em T2. Se adicionamos x e y como filhos de z em T2, obtemos uma codificação 
prefixa para C com custo B(T2) + f(x) + f(y) < B(T), contradizendo a afirmação de T ser 
otimizada. Portanto T1 é otimizada para o alfabeto C1.