09_carteiro_chines_caixeiro_viajante

Prévia do material em texto

Teoria dos Grafos 
 
Problema do Carteiro Chinês e 
Problema do Caixeiro Viajante 
O Problema do Carteiro Chinês 
• Dado um grafo conexo G=(V,E) com pesos nas arestas, 
encontrar um caminho fechado (i.e., com início e fim 
no mesmo vértice) de peso mínimo que atravesse 
cada aresta de G pelo menos uma vez. 
 
• A qualquer caminho fechado (não necessariamente 
de peso mínimo) que atravesse cada aresta de G pelo 
menos uma vez chama-se percurso do carteiro 
Chinês. 
 
• A um caminho nessas condições chama-se percurso 
ótimo do carteiro Chinês. 
O Problema do Carteiro Chinês 
• Problema estudado pela primeira vez por Kwan Mei-Ko em 
1962, relacionado com a distribuição de correspondências 
ao longo de um conjunto de ruas, partindo e terminando 
numa estação de correios. 
 
• Aplicações: 
– Em geral aparece em problemas de atendimento sequencial, 
sobre um conjunto de usuários de um serviço oferecido no 
interior de uma rede de tráfego. 
– Exemplos: 
• Entrega de correspondências 
• Coleta de lixo doméstico 
• Nebulização no combate à dengue 
O Problema do Carteiro Chinês 
• Se o grafo G for Euleriano, então qualquer circuito 
de Euler é um percurso ótimo do carteiro Chinês. 
 
• Se o grafo G não for Euleriano, pode-se construir 
um grafo Euleriano G* duplicando algumas 
arestas de G, selecionadas de forma a conseguir 
um grafo Euleriano com peso total mínimo. 
– A solução exata desse problema pode ser obtida em 
O(n3), como mostram Papadimitriou & Steiglitz (1982). 
O Problema do Carteiro Chinês: 
variações 
• Grafo não orientado: 
– Tem solução em tempo polinomial 
 
• Grafo orientado: 
– Tem solução em tempo polinomial 
 
• Grafo misto (aresta com orientação e arestas sem 
orientação): 
– Não se conhece algoritmo de complexidade 
polinomial. NP-Difícil! 
O Problema do Caixeiro Viajante 
O Problema do Caixeiro Viajante 
O Problema do Caixeiro Viajante 
TSP: Heurística do Vizinho Mais Próximo 
TSP: Heurística do Vizinho Mais Próximo 
TSP: Heurística do Vizinho Mais Próximo 
TSP: Heurística do Vizinho Mais Próximo 
TSP: Heurística do Vizinho Mais Próximo 
TSP: Heurística do Vizinho Mais Próximo 
TSP: Heurística do Vizinho Mais Próximo 
TSP: Heurística do Vizinho Mais Próximo 
TSP: Heurística do Vizinho Mais Próximo 
TSP: Heurística do Vizinho Mais Próximo 
TSP: Heurística do Vizinho Mais Próximo 
TSP: Heurística do Vizinho Mais Próximo 
TSP: Heurística do Vizinho Mais Próximo 
Referências 
• Slides do professor Antonio Alfredo Ferreira 
Loureiro, DCC/UFMG, Projeto e Análise de 
Algoritmos, 2010. 
• Slides do professor Thiago Ferreira de 
Noronha, DCC/UFMG, Heurísticas e 
Metaheurísticas, 2010. 
• Grafos. Conceitos, Algoritmos e Aplicações. 
Goldbarg, 2012.