Algoritmos de aproximação
Aula adaptada do seminário apresentado pelo mestrando
Luiz Josué da Silva Filho
Roteiro
•
•
Motivação
Definições
1. Razão de aproximação
2. Esquema de aproximação
•
Problemas
1.
2.
3.
4.
Cobertura de vértices
Caixeiro viajante
Cobertura de conjuntos
Soma de subconjuntos
Motivação
Motivação
• Muitos problemas de significância prática
são NP-completos
• Três abordagens:
 Entradas pequenas
 Isolamento de casos especiais solúveis em
tempo polinomial
 Pode ser possível achar soluções próximas
da solução ótima
Problema de otimização
• Em um problema de otimização onde cada solução
viável tem associada um custo positivo, deseja-se
achar uma solução próxima da ótima.
• Dependendo da natureza do problema, a solução
ótima pode ser definida como um custo máximo ou
mínimo possível.
Definições
Razão de aproximação
• Suponha que em um problema de otimização:
 cada solução potencial tem um custo
 e deseja-se encontrar uma solução próxima da ótima
  (n) determina a medida de aproximação do
algoritmo
Razão de aproximação:
C C*
max( * , )   (n)
C C
em função da entrada de tamanho n.
Razão de aproximação
• Para muitos problemas foram
desenvolvidos algoritmos polinomiais:
 Com razão pequena constante
 Com razões que crescem em função do tamanho da
entrada
• Há algoritmos que produzem razões muito
pequenas mas ao custo de um tempo de
computação muito alto.
Esquema de aproximação
• É um algoritmo de aproximação que:
 toma como entrada uma instancia do problema
 e um valor ε > 0
• tal que para um ε fixo
 o esquema é um algoritmo (1+ ε)-aproximação.
• Um esquema de aproximação de tempo
polinomial (PTAS) é um esquema que
 para qualquer ε>0 fixo o esquema executa em tempo
polinomial em função do tamanho n da entrada.
Esquema de aproximação
• O tempo de execução de um esquema de aproximação
em tempo polinomial pode crescer tão rápido quanto ε
decresce.
 Ex:
2
O (n  )
• O ideal é que o tempo seja polinomial tanto em 1/ε
quanto em n.
• Em um esquema de aproximação de tempo
completamente polinomial (FPTAS) tanto o esquema
quanto seu tempo de execução são polinomiais em 1/ε e
n.
 Ex:
O((1 /  ) 2 n3 )
Problemas
O problema de cobertura de vértices
• É um problema NP-completo
• A cobertura de vértices de um grafo não direcionado
G  (V,E) é um subconjunto V’ de V tal que se (u , v )
é uma aresta de G, então u está em V’ ou v está em
V’ (ou os dois).
• O problema consiste em achar uma cobertura
de tamanho mínimo dado um grafo nãodirecionado.
• Tal cobertura é uma cobertura de vértices
ótima
Exemplo
O algoritmo
1.
2.
3.
4.
5.
6.
7.
8.
INPUT G // grafo não direcionado
C←{}
E’ ← E[G]
while E’ is not empty do
Let (u,v) be an arbitrary edge of E’
C ← C U {u, v}
Remove from E’ every edge incident on either u or v
return C
Execução
Aproximação do algoritmo
• O algoritmo é 2-aproximação em tempo polinomial
• Prova:
 Faça A denotar as arestas tomadas na linha 5.
 C* deve incluir pelo menos um terminal de cada aresta em A.
 Todas as arestas incidentes nos terminais da aresta escolhida
são removidas de E’ na linha 7.
 Como não há duas arestas cobertas pelo mesmo vértice de C*,
então temos um limite inferior:
| C | A
*
Aproximação do algoritmo
 Cada execução da linha 5 toma uma aresta os quais nenhum de
seus terminais (vértices) já está em C, o que nos leva a um limite
superior:
| C | 2 | A |
Que nos leva a:
| C | 2 | A | 2 | C* |
O problema do caixeiro viajante
• Dado um grafo não direcionado G  (V,E) onde
existe um custo associado a cada aresta. Deve-se
achar um ciclo hamiltoniano de G com um custo
mínimo. Assim
c( A) 
 c(u, v)
( u ,v )A
onde A é um subconjunto das arestas de G.
Desigualdade triangular
• É comum em muitas aplicações verificar a
propriedade da desigualdade triangular
c(u, w)  c(u, v)  c(v, w)
• É provado que o problema do caixeiro viajante é
NP-completo mesmo verificando-se a propriedade
da desigualdade triangular para a função de custo.
O problema do caixeiro viajante com
desigualdade triangular
•
•
Computa-se uma MST o qual o peso é um limite
inferior em função do tamanho de uma solução
ótima do TSP.
O custo do ciclo será no máximo duas vezes o peso
da MST
Approx-TSP-Tour(G, c)
1. select root vertex r in V[G]
2. T = MST-Prim(G, c, r) // computes a MST
3. L = list of vertices in preorder traversal of T
4.
return hamiltonian cycle with vertices ordered as in L
O problema do caixeiro viajante com
desigualdade triangular
O problema do caixeiro viajante com
desigualdade triangular
• Approx-TSP-Tour é um algoritmo 2-aproximação em tempo
polinomial.
• Prova:
 Faça H* ser o ciclo ótimo para o dado conjunto de vértices.
 Como a MST T é obtida pela deleção de arestas, o peso de T é
um limite inferior com relação ao custo de H*. Temos:
c(T )  c( H * )
 Um caminho completo W de T :
a,b,c,b,h,b,a,d,e,f,e,g,e,d,a
O problema do caixeiro viajante com
desigualdade triangular
 W percorre as arestas de T duas vezes, logo
c(W )  2c(T )
 Das equações anteriores temos:
c(W )  2c( H * )
 W não é um ciclo hamiltoniano, mas pela desigualdade triangular:
H = {a,b,c,h,d,e,f,g}
 H é a pré-ordem de T e também é um ciclo hamiltoniano. Como H
é obtido deletando-se vértices de W, temos c( H )  c(W )
 Assim:
c( H )  2c( H * )
O problema de cobertura de conjuntos
• Uma instância (X,F) do problema de cobertura de
conjuntos consiste em:
 um conjunto finito X
 uma família F de subconjuntos
 tal que todo elemento em X pertence a pelo menos um
subconjunto em F:
X  S
SF
 É dito que um subconjunto S  F cobre seus elementos.
O problema de cobertura de conjuntos
 O problema é achar um subconjunto de tamanho mínimo,
c  F tal que seus membros cubram todos os eltos de
X.
X  S
Sc
F  {s1 , s2 , s3 , s4 , s5 , s6}
c  {s3 , s4 , s5}
Um algoritmo de aproximação guloso
GREEDY-SET-COVER(X,F)
1. U = X
2. C = 
3. while U   do
4. select S є F that maximizes | S ∩ U |
5. U = U - S
6. C = C U {S}
7. return C
c  {s1 , s4 , s5 , s3}
Um algoritmo de aproximação guloso
GREEDY-SET-COVER é um algoritmo ρ(n)-aproximação onde
 (n)  H (max{|S |: S  F})
onde H(d) corresponde ao d-ésimo número harmônico:
d
Hd   1
i 1
i
Um algoritmo de aproximação guloso
• Prova:
 Atribui-se um custo de 1 a cada conjunto selecionado
pelo algoritmo
 Distribui-se este custo para os elementos cobertos
pela primeira vez
 Utiliza-se estes custos para derivar o relacionamento
desejado entre:
 o tamanho de uma cobertura de conjuntos ótima C*
 e o tamanho do conjunto de cobertura C retornado pelo
algoritmo
Um algoritmo de aproximação guloso
 Faça-se Si o i-ésimo subconjunto selecionado pelo algoritmo
 O custo de 1 é atribuído ao adicionar-se Si a C.
 Distribui-se este custo aos elementos cobertos pela primeira
vez:
 Tome Cx o custo alocado ao elemento x para cada
 O custo só é atribuído uma vez a x.
 Se x é coberto a primeira vez por Si, então:
cx 
1
| Si  ( S1  S2  ... Si 1 ) |
x X
Um algoritmo de aproximação guloso
 A cada passo do algoritmo uma unidade de custo é atribuída,
então:
| C |  Cx
xX
 O custo atribuído a cobertura ótima é:
 c
SC *xS
x
 E como cada x está em pelo menos um conjunto
 c   c
SC*xS
x
xX
x
S C*
Um algoritmo de aproximação guloso
 Então:
| C |
 c
SC*xS
x
 Como para qualquer conjunto S pertencente a família F temos:
c
xS
x
 H (| S |)
 Assim: (desigualdade (1))
| C |
 H (| S |)
SC *
| C || C * | H (max{|S |: S  F})
Resta-os mostrar a desigualdade (1) :
Livro do Cormen (seção 37.3)
Vamos demonstrar no quadro.....
O problema da soma de subconjuntos
• Uma instância do problema da soma de
subconjuntos é a seguinte:
 Dado um par (S,t), onde S é um conjunto {x1,x2,...,xn}
de inteiros positivos e t é um inteiro positivo.
• Este problema de decisão questiona se existe
um subconjunto de S que tendo seus valores
adicionados somam exatamente o valor de t.
• Este problema é NP-Completo.
O problema da soma de subconjuntos
• No problema de otimização associado:
Deseja-se encontrar um subconjunto
{x1,x2,...,xn} cujo a soma de seus elementos
aproxima-se o máximo mas não supera t.
O algoritmo
EXACT-SUBSET-SUM(S, t)
1. n ← |S|
Soma xi a todos os
elementos da lista Li-1
2. L0 ← {0}
3. for i ← 1 to n do
4.
Li ← MERGE-LISTS(Li-1, Li-1 + xi)
5.
remove from Li every element that is greater than t
6. return the largest element in Ln
•
É um algoritmo exponencial, mas em alguns casos especiais é polinomial
Outro algoritmo
• Pode-se derivar um esquema de
aproximação em tempo polinomial
completo.
Realiza-se um “trimming” de cada lista após
sua criação.
?
Trimming
• Idéia:
Se dois valores em uma lista são próximos o
suficiente,
para o propósito se encontrar uma solução
aproximada,
não há necessidade de manter-se os dois
explicitamente
Trimming
 Utiliza-se um parâmetro δ tal que 0 < δ < 1.
 Então remove-se da lista L tantos elementos quanto
for possível,
 de forma que para cada y removido em L exista um
z na lista resultante que se aproxima de y, tal que:
y
z y
1 
Trimming
 Exemplo:
 Dado L = {10,11,12,15,20,21,22,23,24,29} e δ = 0,1
 Após realizarmos Trim em em L teremos:
L’ = {10,12,15,20,23,29}
 onde:
 11 está representado por 10
 21 e 22 estão representados por 20
 24 está representado por 23
 Complexidade Ө(n)
Trimming
TRIM(L, δ)
1.
m ← |L|
2.
L′ ← {y1}
3.
last ← y1
4.
for i ← 2 to m do
5.
if yi > last * (1 + δ) // yi ≥ last because L is
sorted
6.
then append yi onto the end of L′
7.
last ← yi
8.
return L′
SUBSET-SUM aproximada
APPROX-SUBSET-SUM(S, t,)
1.
2.
3.
4.
5.
6.
7.
8.
•
•
n ← |S|
L0 ← 0
for i ← 1 to n do
Li ← MERGE-LISTS(Li-1, Li-1 + xi)
Li ← TRIM(Li, ε /2n)
remove from Li every element that is greater than t
let z* be the largest value in Ln
return z*
Com 0<ε<1
z* é o valor com 1+ ε o valor da solução ótima
Exemplo
S={104,102,201,101}, t=308, ε=0,40 e δ= ε/8=0,05
linha 2: L0 = {0},
linha 4: L1 = {0, 104},
linha 5: L1 = {0, 104},
linha 6: L1 = {0, 104},
linha 4: L2 = {0, 102, 104, 206},
linha 5: L2 = {0, 102, 206},
linha 6: L2 = {0, 102, 206},
linha 4: L3 = {0, 102, 201, 206, 303, 407},
linha 5: L3 = {0, 102, 201, 303, 407},
linha 6: L3 = {0, 102, 201, 303},
linha 4: L4 = {0, 101, 102, 201, 203, 302, 303, 404},
linha 5: L4 = {0, 101, 201, 302, 404},
linha 6: L4 = {0, 101, 201, 302}
z* = 302 que está dentro dos 40% de aproximação da solução ótima (307)