Caixeiro viajante e Carteiro Chines

Caixeiro viajante e Carteiro Chines

Download
denunciarDenunciarrow
Creative CommonsLicença de uso: BY-NC-SArow

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

Comentários