Análise e Síntese de Algoritmos
Algoritmos de Aproximação
CLRS, Cap. 35
Resumo
• Algoritmos de aproximação
– Algoritmos, com complexidade polinomial, que calculam
soluções aproximadas para problemas de optimização NPdifíceis
• i.e. problemas de optimização cuja formulação como
problema de decisão é NP-completa
2003/2004
Análise e Síntese de Algoritmos
2
Algoritmos de Aproximação
• Motivação
• Definições
• Exemplos de algoritmos de aproximação
– Problemas de optimização cuja formulação de decisão é NPcompleta
• Problema da Cobertura de Vértices
• Problema do Caixeiro Viajante
• Problema da Mochila
• Problema da Cobertura de Conjuntos
2003/2004
Análise e Síntese de Algoritmos
3
Motivação
• Problemas NP-Completos
– Qualquer algoritmo existente demora no pior caso tempo
exponencial no tamanho da instância
• Suporta conjectura P  NP
– Problemas de decisão
• Formulação original requer resposta sim/não
– Problemas de optimização
• Formulação de decisão provada NP-completa
• Encontrar solução óptima é computacionalmente difícil
– Calcular (em tempo polinomial) solução aproximada !
– Mas estabelecer garantias quanto ao valor da solução calculada
2003/2004
Análise e Síntese de Algoritmos
4
Motivação
• Algoritmos de aproximação
– Algoritmos para problemas de optimização NP-completos
(cujas formulações de decisão são NP-completas)
• Algoritmos de tempo polinomial
• Com garantias quanto ao máximo afastamento do valor
calculado face à solução óptima
2003/2004
Análise e Síntese de Algoritmos
5
Definições
• Limite da razão p(n)
– Algoritmo de aproximação para um problema de
optimização
– Para qualquer instância de tamanho n
• Custo da solução calculada, C
• Custo da solução óptima, C*
• max(C/C*, C*/C)  p(n)
– maximização: 0  C  C*
– minimização: 0  C*  C
– p(n)  1
2003/2004
Análise e Síntese de Algoritmos
6
O Problema da Cobertura de Vértices
• Definição:
– G=(V,E), grafo não dirigido
• Cobertura de vértices (VC): conjunto de vértices V’ tal
que qualquer arco em G é incidente em pelo menos um
dos vértices de V’
• O problema VCopt consiste em calcular uma cobertura de
vértices com o número mínimo de vértices
2003/2004
Análise e Síntese de Algoritmos
7
O Problema da Cobertura de Vértices
• Algoritmo de aproximação:
VC-Approx(G)
C=
E’ = E[G]
while E’  
Seja (u, v) arco de E’
C = C  { u, v }
Remover de E’ qualquer arco incidente em u ou v
return C
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
8
O Problema da Cobertura de Vértices
• Teorema:
– VC-Approx é um algoritmo de aproximação com limite da
razão 2 para o problema VCopt
• max(C/C*, C*/C) = C/C*  2
• Prova:
– A: conjunto de arcos seleccionados pelo algoritmo
– Conjunto C é cobertura de vértices
• Ciclo iterado até todos os arcos de E estarem cobertos
– Por inspecção, nenhum par de arcos em A tem vértices
comuns
– Também por inspecção, |C| = 2|A|
2003/2004
Análise e Síntese de Algoritmos
9
O Problema da Cobertura de Vértices
– Cobertura dos arcos em A requer pelo menos um vértice
incidente em cada um dos arcos de A
• Qualquer cobertura de vértices tem que cobrir arcos de A
– Válido também para C*
– |A|  |C*|
– Conclusão:
• |C| = 2|A|  2|C*|
2003/2004
Análise e Síntese de Algoritmos
10
O Problema da Mochila
• Definição:
– Dados n objectos com pesos w1, w2, …, wn e valores v1, v2,
…, vn, e uma mochila que pode transportar peso máximo W,
o problema KNAPSACKopt consiste em identificar os
objectos a transportar, que não excedem o peso máximo W,
e que maximizam o valor dos objectos transportados
2003/2004
Análise e Síntese de Algoritmos
11
O Problema da Mochila
• Algoritmo Greedy:
KNAP-Greedy(w,v,W)
Ordenar w e v tal que v[i]/w[i]  v[j]/w[j] para 1  i  j  n
peso = 0; valor = 0
for i = 1 to n
if peso + w[i]  W
valor += v[i]
peso += w[i]
return valor
• Problema
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
12
O Problema da Mochila
• Algoritmo de Aproximação:
KNAP-Approx(w,v,W)
maior = max {v[i] : 1  i  n}
// Admite-se w[i]  W, 1  i  n
return max {maior, KNAP-Greedy(w,v,W)}
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
13
O Problema da Mochila
• Teorema:
– O algoritmo KNAP-Approx é um algoritmo de aproximação
com limite da razão 2 para o problema KNAPSACKopt
• Prova:
– C*: solução óptima; C: solução retornada pelo algoritmo
– Escolher menor l tal que, l
 wi  W
i 1
– KNAP-Greedy(w,v,W) verifica,
l 1
KNAP - Greedy(w,v, W)   v i
i 1
– E, maior  vl (por definição de maior)
2003/2004
Análise e Síntese de Algoritmos
14
O Problema da Mochila
– Notando que max(x,y)  (x+y)/2, obtemos:
C  max(maior, KNAP - Greedy(w,v, W))
 maior  KNAP - Greedy(w,v, W)) / 2
l 1
l


  v l   v i  / 2   v i / 2  C' / 2


i 1
i 1
 C* /2
– Definição de W ’ e C’:
l
W'   w i
i 1
l
C'   v i
i 1
– Notar que W ’  W e v1/w1  v2/w2  …  vl/wl
• Pelo que C’  C*
– C’ é a solução óptima para W’
2003/2004
Análise e Síntese de Algoritmos
15
O Problema do Caixeiro Viajante
• Definição:
– G=(V,E), grafo completo não dirigido, com função de pesos
w
– Circuito: caminho que visita todos os vértices de G apenas
uma única vez e que termina no vértice de onde começa
• Peso de um circuito: peso do caminho respectivo
– Problema do Caixeiro Viajante (TSP):
• Encontrar o circuito de menor peso em G
– Desigualdade triangular:
• w(t,v)  w(t,u) + w(u,v) para quaisquer arcos (t,v), (t,u) e
(u,v) de G
2003/2004
Análise e Síntese de Algoritmos
16
O Problema do Caixeiro Viajante
• Algoritmo de Aproximação:
TSP-Approx(G,w)
Seleccionar qualquer r  V para vértice raiz
Construir MST T a partir de r
L = lista de vértices resultantes de visita de T em pré-ordem
Definir circuito H que visita vértices de G pela ordem L
return H
• Exemplo
2003/2004
Visita de árvore que lista a raiz antes
dos vértices de cada sub-árvore
Análise e Síntese de Algoritmos
17
O Problema do Caixeiro Viajante
• Teorema:
– O algoritmo TSP-Approx é um algoritmo de aproximação
com limite da razão 2 para instâncias do problema TSP que
verificam a desigualdade triangular
• Prova:
– H*: circuito com custo mínimo
• Provar: C(H)  2C(H*)
– T: MST de G
– W: travessia completa de T
• cada vértice u identificado se visitado pela primeira vez
ou se travessia retorna a u
• W visita cada arco 2 vezes
2003/2004
Análise e Síntese de Algoritmos
18
O Problema do Caixeiro Viajante
– C(T)  C(H*)
• T é MST de G e qualquer árvore abrangente pode ser
obtida a partir de circuito por remoção de 1 arco
– C(W) = 2C(T)
• W atravessa cada arco 2 vezes
– Pelo que,
• C(W)  2C(H*)
– Ordem dos vértices visitados em W:
• …,t,v,u,…,u,v,t,…
– Desigualdade triangular assegura que podemos apagar um
vértice que o custo total não aumenta
• E.g.: com …,t,v,u,…,u,t,… custo total não aumenta
2003/2004
Análise e Síntese de Algoritmos
19
O Problema do Caixeiro Viajante
– Repetir processo de remoção de vértices até cada vértice
ser visitado apenas 1 vez
• Obtém-se ordem dos vértices após visita em pré-ordem
– Circuito resultante, H, visita todos os vértices de G e verifica:
• C(H)  C(W)  2C(H*)
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
20
O Problema da Cobertura de Conjuntos
• Definição:
– Uma instância (X,F) do problema de cobertura de conjuntos
consiste de:
• Conjunto finito X
• Família de subconjuntos de X, F
• Tal que, X = SFS
– O problema da cobertura de conjuntos consiste em
identificar um subconjunto C de F de menor tamanho e tal
que X = SCS
2003/2004
Análise e Síntese de Algoritmos
21
O Problema da Cobertura de Conjuntos
• Algoritmo de Aproximação:
SC-Approx(X,F)
U=X
C=
while U  
Seleccionar S  F que maximiza |S  U|
U=U-S
C=C{S}
return C
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
22
O Problema da Cobertura de Conjuntos
• Teorema:
– O algoritmo SC-Approx tem limite da razão H(max{|S|: S  F}),
com H(d) = 1 + 1/2 + … + 1/d, H(0) = 0
• Prova: (ver folhas)
• Colorário:
– SC-Approx tem limite da razão de ln |X| + 1
• Prova: (ver folhas)
2003/2004
Análise e Síntese de Algoritmos
23
Revisão
• Algoritmos de Aproximação
– Exemplos de algoritmos de aproximação para problemas NPdifíceis
2003/2004
Análise e Síntese de Algoritmos
24