Problema do Caixeiro Viajante
Heurística de Christodes
Heurística de Christodes
Optimização Combinatória
Joana Isabel Silva Lopes Cavadas
4 Junho 2012
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória
Bibliograa
Problema do Caixeiro Viajante
Heurística de Christodes
1
Problema do Caixeiro Viajante
2
Heurística de Christodes
Algoritmo
Exemplo
Teorema
Demonstração
3
Bibliograa
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória
Bibliograa
Problema do Caixeiro Viajante
Heurística de Christodes
Problema do Caixeiro Viajante
Um caixeiro viajante tem de visitar várias cidades, passando por
cada uma uma única vez, e regressar à cidade de onde partiu.
Conhecendo o tempo de percurso directo entre qualquer par de
cidades. Por que ordem as deve visitar de forma a que o tempo
total de percurso seja mínimo?
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória
Bibliograa
Problema do Caixeiro Viajante
Heurística de Christodes
Bibliograa
Heurística de Christodes
A heurística de Christodes permite determinar uma solução para o
Problema do Caixeiro Viajante (PCV) aceitável, ainda que possa
não ser a solução óptima. Apresenta o melhor dos piores casos de
qualquer algoritmo conhecido: produz uma solução cujo custo é, no
máximo, 32 do custo da solução óptima (ver Teorema).
Considere-se um grafo G = (V , E ) completo, onde o custo
associado a cada aresta é não negativo e onde se verica a
desigualdade triangular (isto é, cuv + cvw ≥ cuw , ∀u , v , w ∈ V )
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória
Problema do Caixeiro Viajante
Heurística de Christodes
Bibliograa
Algoritmo
Algoritmo
1
Encontrar, em G = (V , E ) a àrvore geradora de custo mínimo T ;
2
Seja W o conjunto dos vértices de T com grau ímpar e seja M o
emparelhamento perfeito de G [W ] (subgrafo de G induzido por W );
3
Seja agora J = E (T ) ∪ M, conjunto das arestas de um grafo
conexo onde cada vértice tem grau par;
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória
Problema do Caixeiro Viajante
Heurística de Christodes
Bibliograa
Algoritmo
4
Se todos os vértices de J apresentam grau 2, o algoritmo termina e
a solução é dada pelo grafo cujas arestas são J;
4'
Caso contrário, seja v um qualquer vértice com grau, no mínimo, 4
em (V , J ). Então existem arestas uv e vw que se forem excluídas
de J e adicionando a J uw , o subgrafo permanece conexo e ainda
com grau par em todos os vértices. Fazendo este "shortcut"e
repetindo o processo até que todos os vértices tenham apenas 2
arestas, obtemos a solução.
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória
Problema do Caixeiro Viajante
Heurística de Christodes
Bibliograa
Exemplo
Exemplo
Consideremos o grafo G = (V , E ), onde V = {1, 2, 3, 4, 5} são 5
cidades e E os respectivos custos entre cada par.
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória
Problema do Caixeiro Viajante
Heurística de Christodes
Bibliograa
Exemplo
Utilizando o algoritmo de Kruskal, obtem-se a àrvore geradora de
custo mínimo, T :
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória
Problema do Caixeiro Viajante
Heurística de Christodes
Exemplo
Obtem-se assim W = {1, 2, 4, 5} e G [W ] é dada por:
E cujo emparelhamento perfeito é dado pelo conjunto
M = {(1, 4), (2, 5)}
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória
Bibliograa
Problema do Caixeiro Viajante
Heurística de Christodes
Exemplo
Para J = E (T ) ∪ M, tem-se o grafo:
onde o vértice 2 apresenta cardinalidade 4.
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória
Bibliograa
Problema do Caixeiro Viajante
Heurística de Christodes
Exemplo
Procedendo ao "shortcut", retirando (1, 2)(2, 5) acrescentando
(1, 5), obtemos o grafo onde todos os vértices tem grau 2.
Conluindo assim o método heurístico de Christodes, onde a
solução é dada por:
Onde o custo é de 18.
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória
Bibliograa
Problema do Caixeiro Viajante
Heurística de Christodes
Bibliograa
Teorema
Teorema
Suponhamos o PCV com custos não negativos e que satisfazem a
desigualdade triangular. Então, qualquer caminho que seja
construído como solução da heurística de Christodes tem no
máximo 32 do custo de um caminho óptimo.
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória
Problema do Caixeiro Viajante
Heurística de Christodes
Bibliograa
Teorema
Demonstração
Seja H ∗ um caminho óptimo. Retirando qualquer aresta de H ∗
obtem-se uma árvore geradora, deste modo o custo de uma àrvore
geradora mínima T satisfaz: c (T ) ≤ c (H ∗ ).
Considerando o conjunto dos vértices com grau ímpar em T , W , é
possível denir o ciclo C adicionando os vértices pela ordem que
aparecem em H ∗ .
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória
Problema do Caixeiro Viajante
Heurística de Christodes
Bibliograa
Teorema
Demonstração - cont.
|W | é par e o conjunto das arestas de C originam dois
emparelhamentos perfeitos em G [W ]. Uma vez que c satisfaz a
desigualdade triangular, cada aresta destes emparelhamentos não
terá um custo superior ao seu subcaminho denido em H ∗ . Aliás,
∗
um deste emparelhamentos tem um custo no máximo de c (H2 ) .
Deste modo, o custo do emparelhamento
perfeito de custo mínimo
∗
M de G [W ] é no máximo c (H2 ) .
Então: c (J ) ≤ 23 c (H ∗ ). Uma vez que o shortcutting só melhora
c (J ), então o último caminho produzido tem custo, no máximo, de
3
∗
2 c (H ), como queríamos demonstrar.
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória
Problema do Caixeiro Viajante
Heurística de Christodes
Bibliograa
Bibliograa
Cook, William J. ; Cunningham, William H. ; Pulleyblanck, William
C.; Schrijver, Alexander; Combinatorial Optimization;
Wiley-interscience in discrete mathematics and optimization - pg.
245/246.
Joana Isabel Silva Lopes Cavadas
Heurística de Christodes Optimização Combinatória