Algoritmos Aproximados: uma
maneira de se lidar com
problemas NP-completos
Disciplina Análise de Algoritmos
BCC-UFU
Profa. Sandra de Amo
Hierarquia de Aproximação para
Problemas NP-completos
1. Não aproximáveis
Caixeiro Viajante geral
Clique, Conj. Independente
2. Parcialmente aproximáveis
Vertex Cover, Clustering, Caixeiro
Viajante “euclidiano”
3. Totalmente aproximáveis
Mochila, Two-machine scheduling,...
Veremos nesta aula
• Vertex Cover é parcialmente aproximável.
– Algoritmo polinomial aproximado para o Problema do
Vertex Cover
• Caixeiro Viajante “euclidiano” é parcialmente
aproximável.
– Algoritmo polinomial aproximado para o Problema do
Caixeiro Viajante (“euclidiano”)
• Mochila é totalmente aproximável
– Algoritmo polinomial aproximado para o Problema da
Mochila.
Problema do Vertex Cover
Input: Grafo G = (V,E) não-dirigido
Output: Menor V’  V cobrindo todas as arestas de E (qualquer aresta {u,v} tem
uma de suas extremidades em V’)
Vertex Cover é NP-hard
Vertex Cover é parcialmente aproximável.
Ideia geral do algoritmo
aproximado
• Constrói um matching maximal
– Matching = conjunto de arestas que não possuem vértices em
comum
– Matching maximal = se acrescentar mais uma aresta deixa de
ser matching
– Construção do matching maximal: feito em tempo polinomial
• Considera S = vértices do matching maximal
Exemplo
Grafo G
Exemplo
Grafo G
Construindo o matching maximal....
Exemplo
Grafo G
Construindo o matching maximal....
Exemplo
Grafo G
Construindo o matching maximal....
Exemplo
Grafo G
Construindo o matching maximal....
Exemplo
Grafo G
MATCHING MAXIMAL !!
Exemplo
Grafo G
VERTEX COVER PRODUZIDO
PELO ALGORITMO APROXIMADO !!
Exemplo
12 vértices !
Grafo G
VERTEX COVER PRODUZIDO
PELO ALGORITMO APROXIMADO !!
VERTEX COVER OTIMAL : 8 Vértices
Algoritmo realmente aproxima a
solução otimal do VC
Como provar isto SEM conhecer a solução otimal do VC ????
Argumentação:
1. Resultado S do algoritmo é um vertex cover
2. Qualquer outro vertex cover X satisfaz: |S| ≤ 2. |X|
3. Logo |S| ≤ 2. |opt|
4. Além disto: |S| ≥ |opt|
5. Portanto |opt| ≤ |S| ≤ 2.opt
Isto é:
1 ≤ ɑA ≤ 2
Argumentação passo a passo:
1.
Resultado S do algoritmo é um VC
Suponha que não fosse:
Seja e = {u,v} que não é coberta por S, isto é u, v  S
Acrescenta {e} ao matching maximal M (de onde foi obtido o S) =
M  {e} é um matching ! Logo, M não é matching maximal !! Absurdo.
2. Qualquer outro vertex cover X satisfaz: |S| ≤ 2. |X|
Seja X um vertex cover.
|X| ≥ |M| pois X deve cobrir todas as arestas de G
Logo, X deve cobrir as arestas do matching M. Para isto, |X| precisa
incluir pelo menos 1 vértice por aresta de M
Logo, X deve ter pelo menos |M| vértices
Logo, |X| ≥ |S|/2  |S| ≤ 2.|X|
Problema do Caixeiro Viajante
Euclidiano
Input: Conjunto de n cidades C = {c1, c2, ..., cn}, matriz de distâncias simétrica,
satisfazendo a desigualdade triangular : dik ≤ dij + djk
Output: Tour mais curto saindo de c1 e chegando em c1, visitando todas as
cidades uma única vez.
Caixeiro euclidiano é NP-hard
Caixeiro euclidiano é parcialmente aproximável.
Ideia geral do algoritmo
aproximado
• Considera o grafo associado
G = (V,E), onde V = conj. de cidades ; E ´= V x V; custo({i,j}) = dij
• Constrói uma MST de G
• Considera caminho C obtido percorrendo a MST saindo de C1 e
voltando para C1, mesmo que tenha de passar por um trecho mais
de uma vez.
• “Conserta” este caminho C de modo a eliminar revisitas a cidades já
visitadas, inserindo desvios mais curtos a cada vez que o caminho
C vai revisitar uma cidade.
Exemplo
Wichita
Tulsa
Amarillo
Albuquerque
Little Rock
Dallas
Houston
El Paso
San Antonio
Input do Caixeiro Viajante: conjunto de cidades a visitar.
Qual o tour de custo minimo saindo de e voltando para San Antonio ?
Exemplo
Wichita
Tulsa
Amarillo
Albuquerque
Little Rock
Dallas
Houston
El Paso
San Antonio
Grafo completo correspondente ao conjunto de cidades, todas
interligadas.
Exemplo
UMA MST PARA O GRAFO G
Exemplo
Já foi visitado !
Todos foram
visitados !
Pega o atalho
direto para
San Antonio
Percorre a MST, saindo de San Antonio e voltando para San Antonio,
passando por todas as cidades
Exemplo
Já foi visitado !
Tour produzido pelo algoritmo aproximado
Algoritmo realmente aproxima a
solução otimal do Caixeiro Viajante
1.
2.
3.
4.
5.
6.
Considere um tour otimal OPT passando por todas as cidades
uma única vez
Removendo uma aresta de OPT, temos um caminho C que passa
por todos os vértices, sem ciclos = spanning tree
Logo:
Custo de OPT ≥ Custo de C ≥ custo MST
C’ = tour do tipo “ida-e-volta” produzido saindo da raiz e voltando
para a raiz (San Antonio), seguindo a MST
Custo C’ = 2.custo MST ≤ 2.custo OPT
A = caminho produzido pelo algoritmo aproximado
Custo A ≤ Custo C’ (pois A usa atalhos) e
Custo C’ ≤ 2.custo OPT
Logo: 1 ≤ Custo A / Custo OPT ≤ 2
Problema da Mochila
(sem repetição)
Input: W > 0 (capacidade máxima da mochila)
itens 1,2,...,n, pesos p1, p2,..., pn, valores v1, v2,..., vn
Output: Conjunto de itens (sem repetição) com soma total máxima que se
pode carregar na mochila
Mochila é NP-hard – Problema de MAXIMIZAÇÃO
Mochila é Totalmente Aproximável.
Vamos mostrar que para qualquer ε > 0 existe um algoritmo polinomial A tal que
OPT ≤ A (1 + ε / (1 – ε) )
Muito pequeno
Razão de aproximação
ɑ = OPT / A ≤ (1 + ε / (1 – ε) )
Ideia do Algoritmo
•
Ideia central:
– considerar o algorimo de Programação Dinâmica O(nV) que resolve o problema
da mochila sem repetição (ver exercicio 3 – lista Aula 26-27), onde V = total dos
valores dos itens disponíveis.
– Aplicar este algoritmo sobre os valores escalados de modo que a
complexidade em V não seja muito grande !
– Ex. se os valores são v1 = 202.479, v2 = 40.000, v3 = 87.500
considera-se os valores v’1 = 202, v’2 = 40, v’3 = 87 e aplica-se o algoritmo
O(nV) para estes valores.
– Os artigos retornados por este algoritmo caberão na mochila, já que os pesos
não foram alterados.
– Tais artigos podem não corresponder à solução optimal, mas o valor total
(original) dos itens propostos pelo algoritmo aproximado ficará bem
próximo do valor optimal.
Algoritmo
Seja ε > 0 dado.
Consideramos o Algoritmo A (abaixo) que vai aproximar a solução otimal K*
da Mochila de um fator ɑ ≤ 1 + ε(1- ε)
Escala
vi ≤ vi. n/ ε.vmax
Logo: vi ≥ vi ε.vmax/n
Complexidade de A
• Complexidade de A = O(nV’), onde V’ = soma total dos valores dos
itens escalonados.
• Para todo i : v’i ≤ vi . n/ε.vmax ≤ vmax. n/ε.vmax = n/ε
• Logo V’ = Σ v’i ≤ Σ n/ε = n2/ε
• Logo O(nV’) ≤ O(n3/ε) : polinomial em n
Algoritmo A realmente aproxima a solução optimal
de um fator ≤ 1 + ε / (1 – ε)
•
•
•
Suponha que a solução otimal OPT com os valores originais consiste em
selecionar um conjunto S de itens com valor total K*
Consideramos os valores escalonados dos itens considerados na
solução OPT
Vamos analisar qual a relação entre o total destes valores
escalonados e o valor otimal K*
Algoritmo A realmente aproxima a solução optimal
de um fator ≤ 1 + ε / (1 – ε)
•
•
•
Suponha que a solução otimal fornecida pelo algoritmo A sobre os itens
com valores escalonados consiste em selecionar um conjunto S de itens,
com soma total maximal
Consideramos os valores originais dos itens considerados na solução de A e
a soma de seus valores
Vamos analisar qual a relação entre o total destes valores originais
(resultado de A) e o valor optimal K*
≥
≥ Pois S^ é o optimal para A
K* - ε K*
Algoritmo A realmente aproxima a solução optimal
de um fator ≤ 1 + ε / (1 – ε)
•
Logo:
OPT
A
Fator de aproximação = ɑ = OPT/A ≤ 1/(1 – ε) = 1 + (1/(1 – ε) – 1) = 1 + ε / (1 – ε)