Problema do Caixeiro Viajante

Universidade do sul de santa catarina
DANYELLE G. SILVA

PROBLEMA DO CAIXEIRO VIAJANTE

Palhoça
2013

sumário
1 introdução 4 O problema do caixeiro viajante é um dos mais conhecidos e estudados na área de otimização matemática combinatória, estando dessa forma diretamente ligada ao ciclo hamiltoniano. O problema tenta determinar a menor rota para percorrer uma série de cidades, retornando a cidade de origem. Visitando cada cidade exatamente uma única vez, com o objetivo de encontrar a maneira mais barata de visitar todas as cidades e voltar ao seu ponto de origem. 4 Embora possa ser explicado de forma simples o Problema do Caixeiro Viajante (PCV) pertence à classe dos problemas NP-Completo inspirado na necessidade dos vendedores em realizar entregas em diversos locais (as cidades) percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os possíveis custos com transporte e combustível. 4 Segundo os teoremas até então apresentados, é improvável existir um algoritmo rápido para a resolução do problema do caixeiro viajante. 4
2 O PROBLEMA DO CAIXEIRO VIAJANTE 4 Antigamente muitos vendedores, chamados de caixeiros viajantes, ganhavam a vida oferecendo seus produtos em diferentes cidades. Imagine que um caixeiro viajante escolhesse algumas cidades e precisasse encontrar o caminho mais curto para suas andanças. Esse é um problema matemático, conhecido como o problema do caixeiro viajante (PCV). 4
2.1 O PROBLEMA DO CAIXEIRO VIAJANTE COM DESIGUALDADE DE TRIÂNGULOS 5
2.2 O PROBLEMA GERAL DO CAIXEIRO VIAJANTE 7
3 CONCLUSÃO 8 O problema do caixeiro viajante é uma importante questão da área de otimização matemática. Tem grande relevância para o campo da logística e da produção, além de outros. 8 Seu principal objetivo é encontrar uma rota que possa percorrer todas as cidades uma única vez de forma que regresse ao seu ponto de origem. Apesar de sua fácil explicação, o PCV não