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 CoverInput: 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

Grafo G VERTEX COVER PRODUZIDO PELO ALGORITMO APROXIMADO !!

VERTEX COVER OTIMAL : 8 Vértices

12 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 VCSuponha que não fosse: Seja e = {u,v} que não é coberta por S, isto é u, v SAcrescenta {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 GLogo, X deve cobrir as arestas do matching M. Para isto, |X| precisa

incluir pelo menos 1 vértice por aresta de MLogo, X deve ter pelo menos |M| vérticesLogo, |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.

ExemploWichita

Tulsa

Little Rock

Dallas

Houston

San Antonio

El Paso

Albuquerque

Amarillo

Input do Caixeiro Viajante: conjunto de cidades a visitar.Qual o tour de custo minimo saindo de e voltando para San Antonio ?

ExemploWichita

Tulsa

Little Rock

Dallas

Houston

San Antonio

El Paso

Albuquerque

Amarillo

Grafo completo correspondente ao conjunto de cidades, todas interligadas.

Exemplo

UMA MST PARA O GRAFO G

Exemplo

Percorre a MST, saindo de San Antonio e voltando para San Antonio, passando por todas as cidades

Já foi visitado !

Todos foram visitados !Pega o atalhodireto para San Antonio

Exemplo

Já foi visitado !

Tour produzido pelo algoritmo aproximado

Algoritmo realmente aproxima a solução otimal do Caixeiro Viajante1. Considere um tour otimal OPT passando por todas as cidades

uma única vez2. Removendo uma aresta de OPT, temos um caminho C que

passa por todos os vértices, sem ciclos = spanning tree3. Logo: Custo de OPT ≥ Custo de C ≥ custo MST4. C’ = tour do tipo “ida-e-volta” produzido saindo da raiz e voltando

para a raiz (San Antonio), seguindo a MST5. Custo C’ = 2.custo MST ≤ 2.custo OPT6. 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

ɑ = OPT / A ≤ (1 + ε / (1 – ε) ) Razão de aproximação

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*

≥

≥K* - ε K*Pois S^ é o optimal para A

Algoritmo A realmente aproxima a solução optimal de um fator ≤ 1 + ε / (1 – ε)

• Logo:

OPTA

Fator de aproximação = ɑ = OPT/A ≤ 1/(1 – ε) = 1 + (1/(1 – ε) – 1) = 1 + ε / (1 – ε)