Problemas de Roteamento: Caixeiro Viajante

Publicado em 11/07/2006

PROBLEMAS DE ROTEAMENTO: Caixeiro Viajante

2006


Resumo


O Problema do Caixeiro Viajante é um dos mais clássicos problemas de Complexidade. Se caracteriza por dado um conjunto de n cidades e uma matriz de distâncias distancias [1..n,1..n], fazer com que seja encontrado um caminho que tenha a menor distância a ser percorrida para que sejam visitadas todas as cidades passando exatamente uma única vez em cada cidade e retornando a cidade de origem. O problema do caixeiro viajante é considerado um problema da otimização; além de exibir uma solução é requerida certa qualidade ótima da solução.

Palavras-chaves: caixeiro viajante, otimização, complexidade, distancia.

Abstract

The Traveling Salesman Problem is one of the most classic problems of Complexity. It is characterized by a given set of n cities and a matrix of distances distances [l..n, l..n], to find a path that has the lesser distance to be covered so that all the cities are visited, passing exactly once in each city and returning to the city of origin. The Traveling Salesman Problem is considered a problem of the optimization; beyond showing a solution, it is required a certain excellent quality of the solution.


1 – Introdução

O problema do caixeiro viajante (PVC) é um caso típico de otimização combinatória freqüentemente utilizado em computação para demonstrar casos de difícil resolução.

O PCV pode ser definido como o problema de encontrar o roteiro de menor distância ou custo que passa por um conjunto de…

É esse o conteúdo que você precisa?
Faça seu login e saiba como ver o trabalho completo

O Zé Moleza facilita sua vida acadêmica ajudando você em suas pesquisas, e a economizar o seu tempo e o seu dinheiro nos seus trabalhos de faculdade. São mais de 26144 pesquisa acadêmicas entre elas, monografia, temas de monografias, TCC, modelos de monografias, trabalhos de universidades, resenha, Paper, Ensaio, Bibliografia, Trabalhos Escolares.

Dicas de como fazer: Capa de Monografia, capa de TCC, Regras da ABNT, como fazer monografia, como fazer Projeto Final, como fazer seminário, como fazer capas, referências bibliográficas, modelo de monografia.

O Zé Moleza NÃO faz a venda de monografia e É TOTALMENTE CONTRA a compra de monografia pronta e trabalhos prontos. O Zé Moleza NÃO auxilia a quem compra monografia, NÃO apóia a quem quer comprar Trabalhos Prontos, e NÃO APROVA a quem quer comprar TCC prontos, dando dicas de formatação, regras da ABNT, dando sugestões de temas para monografia, resumo de livros, projeto de pesquisa, projeto de mestrado, projeto de pós-graduação, trabalhos acadêmicos, incentivando o usuário a desenvolver por conta própria sua monografia.