Algoritmos de Aproximação para o Problema do Caixeiro Viajantecris/aulas/08_1_338/slides/aula27-2.pdf · ciclo euleriano: passeio fechado que passa ... Dobre as arestas da árvore

Algoritmos de Aproximação para o

Problema do Caixeiro Viajante

24 de agosto de 2004

TSP – p.1/19


Dadosgrafo

�

comprimento

�� da aresta

��

(

� � � � )

Circuito hamiltoniano: circuito que passa por todos os vértices

Problema (TSP): Dados e , encontrar circuitohamiltoniano em de comprimento mínimo.

TSP – p.2/19


Dadosgrafo

�

comprimento

�� da aresta

��

(

� � � � )


Problema (TSP): Dados e , encontrar circuitohamiltoniano em de comprimento mínimo.

TSP – p.2/19


Dadosgrafo

�

comprimento

�� da aresta

��

(

� � � � )


Problema (TSP): Dados

�

e

�

, encontrar circuitohamiltoniano

�

em

�

de comprimento

� � � �

mínimo.

TSP – p.2/19

Variantes do Caixeiro Viajante

TSP métricografo completofunção comprimento

�

satisfazdesigualdade triangular:

��

��

� � �

ji

k

TSP euclideanoCaso particular do métricoVértices são pontos no plano(ou num espaço euclideano qq de dimensão fixa)

é a distância euclideana entre e

TSP – p.3/19

Variantes do Caixeiro Viajante

TSP métricografo completofunção comprimento

�

satisfazdesigualdade triangular:

��

��

� � �

ji

k

TSP euclideanoCaso particular do métricoVértices são pontos no plano(ou num espaço euclideano qq de dimensão fixa)

�� é a distância euclideana entre

�

e

�

TSP – p.3/19

Resultados Conhecidos

NP-difícil mesmo se

��

� � ��

� �

para toda aresta � [GJ79]

Difícil de aproximar [SG76]

� � �

-aproximação para o caso métrico [C76]

PTAS para o caso euclideano [A98,M99]

Nesta aula:

-aproximação para o caso métrico [RSL77]

-aproximação para o caso métrico

Comentários sobre o PTAS do caso euclideano

TSP é difícil de aproximar

TSP – p.4/19

Resultados Conhecidos

NP-difícil mesmo se

��

� � ��

� �

para toda aresta � [GJ79]

Difícil de aproximar [SG76]

� � �

-aproximação para o caso métrico [C76]

PTAS para o caso euclideano [A98,M99]

Nesta aula:

�

-aproximação para o caso métrico [RSL77]

� � �

-aproximação para o caso métrico

Comentários sobre o PTAS do caso euclideano

TSP é difícil de aproximar

TSP – p.4/19

-aproximação p/o TSP Métrico

(1) Árvore geradora de comprimento mínimo (polinomial)(2) Dobre as arestas da árvore (todos os vértices tem grau par)(3) Obtenha ciclo euleriano

�

(polinomial)ciclo euleriano: passeio fechado que passaexatamente uma vez por cada aresta(4) Obtenha de

�

circuito hamiltoniano

�

(5) Devolva

�

(2) Dobre as arestas da árvore (todos os vértices tem grau par)(3) Obtenha ciclo euleriano (polinomial)ciclo euleriano: passeio fechado que passaexatamente uma vez por cada aresta(4) Obtenha de circuito hamiltoniano(5) Devolva

TSP – p.5/19



�


�


�

(5) Devolva

�

(3) Obtenha ciclo euleriano (polinomial)ciclo euleriano: passeio fechado que passaexatamente uma vez por cada aresta(4) Obtenha de circuito hamiltoniano(5) Devolva

TSP – p.5/19



�


�


�

(5) Devolva

�

(4) Obtenha de circuito hamiltoniano(5) Devolva

TSP – p.5/19



�


�


�

(5) Devolva

�

(5) Devolva

TSP – p.5/19



�


�


�

(5) Devolva

�

(5) Devolva

TSP – p.5/19



�


�


�

(5) Devolva

�

(5) Devolva

TSP – p.5/19



�


�


�

(5) Devolva

�

(5) Devolva

TSP – p.5/19



�


�


�

(5) Devolva

�

(5) Devolva

TSP – p.5/19



�


�


�

(5) Devolva

�

(5) Devolva

TSP – p.5/19



�


�


�

(5) Devolva

�

(5) Devolva

TSP – p.5/19



�


�


�

(5) Devolva

�

(5) Devolva

TSP – p.5/19



�


�


�

(5) Devolva

�

(5) Devolva

TSP – p.5/19



�


�


�

(5) Devolva

�TSP – p.5/19

-Aproximação p/o TSP Métrico

Algoritmo TSPM-Rosenkrantz-Stearn-Lewis

� ��

� �

� �

MST

� ��

� �

� � � � � �

� �

EULER

� � � �

� �

ATALHO

� � �

devolve

�

Tempo de execução:

: o número de vértices de: o número de arestas de

TSP – p.6/19


Algoritmo TSPM-Rosenkrantz-Stearn-Lewis

� ��

� �

� �

MST

� ��

� �

� � � � � �

� �

EULER

� � � �

� �

ATALHO

� � �

devolve

�

Tempo de execução: � ��

� : o número de vértices de

�

�: o número de arestas de

�

TSP – p.6/19


Delimitação inferior para opt: opt

� � � � �

onde

�

é árvore geradora de comprimento mínimo

Prova:: circuito hamiltoniano de comprimento mínimo

: aresta deé árvore geradora

opt

Teorema: TSPM-Rosenkrantz-Stearn-Lewis é uma-aproximação polinomial para o TSP métrico.

Prova: opt

TSP – p.7/19



� � � � �

onde

�


Prova:

� �

: circuito hamiltoniano de comprimento mínimo

�: aresta de

� �

� �

� � é árvore geradora

opt


Prova: opt

TSP – p.7/19



� � � � �

onde

�


Prova:

� �


�: aresta de

� �

� �


opt � � � � � � � � � � �

� � � � � � � ��

�


Prova: opt

TSP – p.7/19



� � � � �

onde

�


Prova:

� �


�: aresta de

� �

� �


opt � � � � � � � � � � �

� � � � � � � ��

�

Teorema: TSPM-Rosenkrantz-Stearn-Lewis é uma

�

-aproximação polinomial para o TSP métrico.

Prova: opt

TSP – p.7/19



� � � � �

onde

�


Prova:

� �


�: aresta de

� �

� �


opt � � � � � � � � � � �

� � � � � � � ��

�

Teorema: TSPM-Rosenkrantz-Stearn-Lewis é uma

�

-aproximação polinomial para o TSP métrico.

Prova:

� � � � � � � � �

� � � � � �

� � � � � � � �

opt�

�

TSP – p.7/19

Algoritmo de Christofides

(1) Árvore geradora de comprimento mínimo

(2) Emparelhamento perfeito de comprimento mínimo nosubgrafo induzido pelos vértices de grau ímpar (polinomial)

(3) Junte os dois obtendo euleriano(4) Obtenha ciclo euleriano de(5) Obtenha de circuito hamiltoniano(6) Devolva

TSP – p.8/19






TSP – p.8/19






TSP – p.8/19




(3) Junte os dois obtendo� �

euleriano



TSP – p.8/19




(3) Junte os dois obtendo� �

euleriano(4) Obtenha ciclo euleriano

�

de

� �



TSP – p.8/19




(3) Junte os dois obtendo

� �


�

de

� �

(5) Obtenha de�


�

(6) Devolva

TSP – p.8/19




(3) Junte os dois obtendo

� �


�

de

� �

(5) Obtenha de�


�

(6) Devolva�

TSP – p.8/19


Algoritmo TSPM-Christofides

� ��

� �

� �

MST

� ��

� �

� � conjunto de vértices de grau ímpar de

�

�

EDMONDS

� � � � ��

� �

� � � � �

� �

EULER

� � � �

� �

ATALHO

� � �

devolve

�

(

� � � �

: subgrafo de

�

induzido por

�

)

Tempo de execução:( : o número de vértices de )

TSP – p.9/19


Algoritmo TSPM-Christofides

� ��

� �

� �

MST

� ��

� �

� � conjunto de vértices de grau ímpar de

�

�

EDMONDS

� � � � ��

� �

� � � � �

� �

EULER

� � � �

� �

ATALHO

� � �

devolve

�

(

� � � �

: subgrafo de

�

induzido por

�

)

Tempo de execução: � �

(� : o número de vértices de

�

)

TSP – p.9/19


Uma segunda delimitação para opt: opt

� � � � �

onde é e. p. de comprimento mínimo em� � � �

Pr: : circuito hamiltoniano de comprimento mínimo: conj. vért. de grau ímpar de ( é par): circuito induzido por em

determina dois e. p. em : e

TSP – p.10/19



� � � � �


Pr:

� �


�

: conj. vért. de grau ímpar de

�

(

� � �

é par)

� �

: circuito induzido por

� �

em�

: circuito induzido por em


TSP – p.10/19



� � � � �


Pr:

� �


�


�

(

� � �

é par)

� �


� �

em�


TSP – p.10/19



� � � � �


Pr:

� �


�


�

(

� � �

é par)

� �


� �

em�

� �

determina dois e. p. em

� � � �

: � e �

TSP – p.10/19



� � � � �


.

Prova:

� � � � � � �

��

��

� � � � � �

� � � � � �

(pela desigualdade triangular)

� opt �

�

TSP – p.11/19


Teorema: TSPM-Christofides é uma

��

�

-aproximaçãopolinomial para o TSP métrico.

Prova:

opt opt

opt

Melhor algoritmo de aproximação conhecidopara o TSP métrico.

TSP – p.12/19



��

�


Prova: � � � � � � � � �

� � � � � �

� � � � � � � � �

�

opt ��

� opt

�

�� opt �

�


TSP – p.12/19



��

�


Prova: � � � � � � � � �

� � � � � �

� � � � � � � � �

�

opt ��

� opt

�

�� opt �

�


TSP – p.12/19


A análise é justa.

Christofides

vérticesComprimento:

Circuito ótimo

Comprimento:

TSP – p.13/19



Christofides

�� vértices

Christofides


Circuito ótimo

Comprimento:

TSP – p.13/19



Christofides

�� vértices


Circuito ótimo

Comprimento:

TSP – p.13/19



Christofides

�� vérticesComprimento:

��

Circuito ótimo

Comprimento:

TSP – p.13/19



Christofides

�� vérticesComprimento:

��

Circuito ótimo

Comprimento:��

TSP – p.13/19

TSP Euclideano

PTAS: esquema de aproximação polinomial

� � ��

-aproximação polinomial para todo� � �

fixo

Arora’96 e Mitchel’96: PTAS para o TSP euclideano

Idéia:

TSP – p.14/19

TSP Euclideano


� � ��


fixo


Idéia:

PSfrag replacements portal

TSP – p.14/19

TSP Euclideano


� � ��


fixo


Idéia:


TSP – p.14/19

TSP Euclideano


� � ��


fixo


Idéia:


TSP – p.14/19

TSP Euclideano


� � ��


fixo


Idéia:


TSP – p.14/19

TSP Euclideano


� � ��


fixo


Idéia:

Circuito que respeita portal: entra e sai dos quadrados dadissecção através de portais.

Algoritmo: Encontra um circuito hamiltoniano mais curtoque respeita os portais por programação dinâmica.

Tal circuito está tão próximo quando se queirade um TSP tour.

TSP – p.15/19

Resultado de Inaproximabilidade

��

função polinomialmente computável

Teorema (Sahni e Gonzalez ’76): Se existir

� ��

-aproximação polinomial p/o TSP� ��

� �, onde � � �

� � �

,então P=NP.

Problema HC: Dado , decidir se tem ou não um circuitohamiltoniano.

NP-completo [K72]

TSP – p.16/19


��

função polinomialmente computável


� ��

-aproximação polinomial p/o TSP� ��

� �, onde � � �

� � �

,então P=NP.

Problema HC: Dado

�

, decidir se

�

tem ou não um circuitohamiltoniano.

NP-completo [K72]

TSP – p.16/19



� ��

-aproximação polinomial p/o TSP

� ��

� �

, onde � � ��

,então P=NP.Pr: � � � ��

-aproximação polinomial p/o TSP � �

�

� �

algoritmo polinomial p/o HC � �


algoritmo polinomial p/o HCAlgoritmo

grafo completo empara cada em façapara cada em faça

seentão devolva “Sim”então devolva “Não”

TSP – p.17/19



� ��


� ��

� �

, onde � � ��



�

� �


Algoritmografo completo em

para cada em façapara cada em faça

seentão devolva “Sim”então devolva “Não”

TSP – p.17/19



� ��


� ��

� �

, onde � � ��



�

� �


Algoritmo

� ��

� � grafo completo em

��para cada � em

� � faça� � �

para cada � em

� � � � � faça

� � ��

� � � � ��

se

� � ��

então devolva “Sim”então devolva “Não”

TSP – p.17/19


�

polinomial � �

polinomial

se existe circuito hamiltoniano em ,então opt e

opt

se não existe circuito hamiltoniano em ,então

pois qq circ. hamilt. usa(i.e., ).

TSP – p.18/19


�

polinomial � �

polinomial

se existe circuito hamiltoniano em

�

,então opt �

� � �

e

� � � � � � � � � � �

opt � � � � � � � � � ��

se não existe circuito hamiltoniano em ,então

pois qq circ. hamilt. usa(i.e., ).

TSP – p.18/19


�

polinomial � �

polinomial

se existe circuito hamiltoniano em

�

,então opt �

� � �

e

� � � � � � � � � � �

opt � � � � � � � � � ��

se não existe circuito hamiltoniano em

�

,então

� � � � � � � � � � � � � � � �

pois qq circ. hamilt. usa � ��

(i.e.,

�� ).

�

TSP – p.18/19

Para completar...

Blabla

PSfrag replacements

POFPTAS PTAS APX

NPO

TSPTSP MétricoTSP Euclideano

TSP – p.19/19

Documents

Algoritmos de Aproximação para o Problema do Caixeiro Viajantecris/aulas/08_1_338/slides/aula27-2.pdf · ciclo euleriano: passeio fechado que passa ... Dobre as arestas da árvore