apresentação caixeiro

Prévia do material em texto

O problema do
"caixeiro viajante"
Anderson Silvestre
Dayanna Carina
Felipe Resende
Izabelle Moreira
Philipe Perdigão
Proposta
• Um caixeiro viajante, partindo de sua cidade, deve visitar exatamente uma 
única vez cada cidade de uma dada lista e retornar para casa tal que a 
distância total percorrida seja a menor possível.
Considerações
• Este problema é amplamente discutido e estudado na área de otimização 
matemática.
• Para sua modelagem, propuseram a utilização da estrutura matemática 
denominada grafo.
Definições
• Vértice
• Aresta e seu custo
• Grafo
• Caminho hamiltoniano
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.
Simulação
Comparativo
Vantagens
• Grande aplicação prática;
• Grande relação com outros modelos;
Desvantagens
• Inviabilidade na tentativa de resolução de 
problemas mais complexos;
Aplicações
• Minimização de rotas de veículos;
• Desenvolvimento de sistemas digitais;
• Sequenciamento de atividades;
• Otimização do movimento de ferramentas de corte;
• Otimização da perfuração de furos em placas de circuito impresso;