Administração de carreiras

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

2006/2007

Análise e Síntese de Algoritmos

2

1

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

2006/2007

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
2006/2007 Análise e Síntese de Algoritmos 4

2

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

2006/2007

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

2006/2007

Análise e Síntese de Algoritmos

6

3

O Problema da Cobertura de Vértices
• Definição:
– G=(V,E), grafo não