Caixeiro Viajante e Carteiro Chinês - Complementar

Caixeiro viajante e Carteiro Chines


Campus - Mossoró Profª Adricia Fonseca Mendes
Caminhos que usam todos os vértices ou todas as arestas de um grafo são geralmente chamados de percursos;
Uma grande variedade de problemas práticos podem ser vistos como um percurso num grafo;
Eles se dividem em duas categorias:
o Problemas do tipo euleriano o Problemas do tipo hamiltoniano
Problemas do tipo euleriano: requerem que cada aresta seja percorrida pelo menos uma vez
Problemas do tipo hamiltoniano: requerem que cada vértice seja percorrido pelo menos uma vez
Exemplos clássicos de otimização: o problema do carteiro chinês (C) e o problema do caixeiro viajante (CV)
Os dois problemas parecem ser semelhantes, mas possuem complexidades bem diferentes o A maior parte dos problemas eulerianos são resolvidos em tempo polinomial o A maioria dos problemas hamiltonianos têm uma solução de custo elevado e são classificados como NP- difícil, é necessário a utilização de técnicas aproximativas para se obter um resultado em tempo hábil
Explosão combinatória (CV) 5

O matemático chinês Meigu Guan introduziu o problema em 1962:
o Achar o caminho fechado mais curto que percorra todas as arestas de um grafo pelo menos uma vez o É o problema do carteiro que quer entregar a correspondência numa rede de ruas e retornar ao escritório central o mais rápido possível para se obter um resultado em tempo hábil
Definição: um circuito do carteiro em um grafo G é um caminho fechado que usa cada aresta de G pelo menos uma vez;
Definição: em um grafo com peso nas arestas, um circuito ótimo do carteiro é um circuito do carteiro cujo peso total das arestas é mínimo.
Variações do problema do carteiro chinês aparecem em diversas aplicações:
oColeta de lixo; oLimpeza das ruas; oPintura de linhas no centro das ruas; oPatrulhamento da polícia; oPesquisa de opinião e recenseamento; oPlotagem de uma rede.
(traveling salesman problema – TSP) 9
(traveling salesman problema – TSP) 10
(traveling salesman problema – TSP) 1
(traveling salesman problema – TSP) 12
(traveling salesman problema – TSP) 13