programacao2

Caixeiro Viajante

Caixeiro Viajante
Problema TSP: Dados um grafo G e um custo ce em Q ≥ para cada aresta e, determinar um circuito hamiltoniano C que minimize c(C).
A

A

10

10
5

5

C

C

9

6

9

6
3

B
9

Grafo G

3

B
9

D

D

Circuito Hamiltoniano de G de custo 27

Aplicacoes:
¸˜
• Perfuracao e solda de circuitos impressos.
¸˜
• Determinacao de rotas de custo m´nimo.
¸˜
ı

´
Flavio Keidi Miyazawa (Unicamp)

Algoritmos de Aproximacao
¸˜

Campinas, 2001-2011

67 / 312

Caixeiro Viajante

Resultados Negativos
Teorema: Dado um grafo G, o problema de decidir se G tem um circuito
´
hamiltoniano e NP-completo.
Teorema: N˜ o existe uma α-aproximacao para o TSP, para qualquer valor α, a ¸˜ a menos que P=NP
Prova. Suponha existir α-aproximacao para o TSP.
¸˜
Dado G = (V , E) seja G = (V , E , c ) tal que
•V =V
•E =V ×V
1
se e ∈ E,
• c (e) =
´
α|V | caso contrario
Se G tem circuito hamiltoniano, OPT(G ) = |V |
´
caso contrario, OPT(G ) > α|V |.
ˆ
=⇒ Decidimos existencia de circuito hamiltoniano em G.
´
Flavio Keidi Miyazawa (Unicamp)

Algoritmos de Aproximacao
¸˜

Campinas, 2001-2011

68 / 312

Caixeiro Viajante

´
Caixeiro Viajante Metrico
Def.: Os custos de um grafo satisfazem desigualdade triangular se c(i, j) ≤ c(i, k ) + c(k, j),

∀i, j, k ∈ V

k c(i,k) i

c(k,j) c(i,j) j

´
Problema TSP-Metrico: Dados um grafo G com desigualdade triangular e um custo ce em Q ≥ para cada aresta e, determinar um circuito hamiltoniano C que minimize c(C).

´
Flavio Keidi Miyazawa (Unicamp)

Algoritmos de Aproximacao
¸˜

Campinas, 2001-2011

69 / 312

Caixeiro Viajante

´
Estrategia:
Encontrar ciclo gerador e fazer “shortcuts” (atalhos).
A LGORITMO ATALHO(P),
Trilha fechada P = (v0 , . . . , vm )
1
w0 ← v0
2
3
4
5

n←0

v0 v5 v1

para i de 1 a m faca
¸

v2

se vi ∈ {w0 , . . . , wn }
/
˜ entao n ← n + 1

6

wn ← vi

7