Apresentação Caixeiro Viajante

Prévia do material em texto

O PROBLEMA DO CAIXEIRO VIAJANTE
INTRODUÇÃO
• O Problema do Caixeiro Viajante - PCV é um dos mais tradicionais e conhecidos 
problemas de programação matemática. O objetivo do PCV é encontrar, em um grafo 
G=(V,A), o circuito hamiltoniano de menor custo. 
DEFINIÇÃO
• O PCV e um grafo, numa definição bem simples, são um conjunto de Vértices e Arestas. 
Os vértices (ou nós) são pontos que podem representar cidades, depósitos, postos de 
trabalho ou atendimento. Já as arestas são linhas que conectam os vértices, podendo 
representar ruas ou estradas, por exemplo. 
• Um circuito hamiltoniano é um passeio que percorre todos os vértices de um grafo e 
retorna ao vértice origem (início do passeio), passando por cada vértice apenas uma vez.
• Em 1857 Willian Rowan Hamilton desenvolveu um jogo que se chamou Aroundthe
Word.Esse jogo foi feito em uma figura dodecaedro onde cada vértice da figura estava 
associada a uma cidade importante daquela época. O objetivo desse jogo era encontrar 
um caminho através dos vértices do dodecaedro onde se iniciava de uma cidade e 
terminasse na mesma sem que repetisse a visita em uma mesma cidade. 
O PROBLEMA DO CAIXEIRO VIAJANTE
• O objetivo do Caixeiro Viajante é partir de uma cidade “X”, visitar todas as cidades do 
grafo e retornar à cidade “X”, sendo que todas as cidades sejam visitadas apenas uma 
única vez, com um custo menor.
APLICAÇÕES
• 1° - Minimização de rotas de veículos
• 2° - Otimização de perfuração de furos em placas de circuito impresso
ALGORITMO
• 1º passo: Listar os vértices;
• 2º passo: Definir uma matriz de custos, entre os vértices listados;
• 3º passo: Definir o vértice origem-destino;
• 4º passo: Gerar uma matriz de permutações, com os demais vértices;
• 5º passo: Somar, para cada linha(incluindo o vértice origem-destino) da matriz de 
permutações, o custo total entre os vértices vigentes;
• 6º passo: Comparar o custo total de cada linha e, ao encontrar o menor valor, listar os 
vértices da linha correspondente ao mesmo.
PRINCIPAIS VANTAGENS DO PCV
• É grande sua aplicação prática.
• Quanto menor a quantidade de vértices e arestas o grafo possuir, o grau de 
complexidade e tempo de resolução diminuirá.
• Entre outras.
PRINCIPAIS DESVANTAGENS DO PCV
• Grande dificuldade de solução exata
• Quanto maior a quantidade de vértices e arestas o grafo possuir, o grau de complexidade 
e tempo de resolução aumentará.
• Entre outras.
CONCLUSÃO
• Apresentam-se neste trabalho algumas contribuições para a resolução do Problema do 
Caixeiro Viajante. São grandes os benefícios que essa ferramenta pode nos fornecer, dos 
mais simples aos mais complexos.
• Enfim, o problema ainda está em aberto, e ainda há muito campo para ser explorado, 
tanto em algoritmos genéticos, quanto em algoritmos tradicionais, ou híbridos.