O Caixeiro Viajante

O Caixeiro Viajante*
Daniel Flores Bastos1
1Sistemas de Informação – Centro Universitário Franciscano (UNIFRA)
Caixa Postal 15.064 – 91.501-970 – Santa Maria – RS – Brazil [e-mail] Resumo. Esse artigo aborda o problema do Caixeiro Viajante, conhecido como um problema de distribuição de mercadorias e sua ligação com o conhecimento. Foi feito uma breve pesquisa sobre o assunto, buscando suas características e abordagens utilizadas por outros autores. O Caixeiro Viajante se propõe a encontrar uma rota que visite todos os pontos tendo o menor custo. Ao final é apresentada uma conclusão onde se reforçam conceitos importantes a respeito do assunto.
1. Introdução
Este trabalho tem como objetivo abordar as características sobre o problema do Caixeiro Viajante – PCV. Esse é um dos problemas mais estudados em otimização combinatória devido ao seu custo computacional para encontrar uma única resposta, sendo essa a que possuí o menor custo. O problema do Caixeiro Viajante é um problema muito estudado devido aos diversos ramos de aplicabilidade em nosso cotidiano. Buscando reduzir os custos envolvidos, por exemplo, com o transporte de mercadorias, o Caixeiro Viajante se propõem a encontrar o melhor caminho, que visite todos os pontos desejados, tendo em vista a distância entre os pontos e todas as possíveis combinações de caminhos possíveis,
2. O Problema
Sabendo que um entregador precise visitar duas cidades para fazer suas entregas, há nesse caso, apenas dois possíveis caminhos (AB ou BA), ficando fácil a decisão sobre qual o melhor caminho. Mas o problema está assim que vão sendo adicionados novos pontos à serem visitados. Por exemplo, se o surge uma terceira cidade (a cidade C), nesse caso já lidamos com seis possíveis caminhos (ABC, ABC, BAC, BCA, CAB e CBA).
Para esses casos, em que o custo computacional é alto, e que o tempo para encontrar a melhor resposta inviabiliza a utilização da mesma, é apresentado a técnica Heurística, que em