Problema Caixeiro Viajante



Dado um conjunto de n cidades e a distância (ou custo da viagem) entre elas; o problema consiste em determinar uma rota que percorra cada uma das n cidades uma única vez e retorne à cidade de origem, de tal forma que a distância total percorrida seja mínima.





O interesse por este problema deve-se a sua dificuldade de resolução e também, a sua enorme aplicabilidade na engenharia e nas ciências.
Diversos problemas reais podem ser modelados como um PCV: roteamento de veículos, programação de tarefas em máquinas, perfuração de placas de circuitos integrados, mapeamento do
DNA humano, dentre outras aplicações.



Há inúmeros algoritmos exatos e heurísticos para resolver este problema. Os algoritmos exatos encontram soluções ótimas, mas sua aplicação em problemas de grande dimensão torna-se proibitiva em virtude do elevado esforço computacional. Isto se deve ao fato do
PCV pertencer a classe de problemas
NP-Completo.



Pode-se dizer que os problemas de NPcompleto são os problemas mais difíceis de NP e muito provavelmente não formem parte da classe de complexidade P. A razão é que se conseguisse encontrar uma maneira de resolver qualquer problema NP-completo rapidamente (em tempo polinomial) , então poderia ser utilizado algoritmos para resolver todos problemas NP rapidamente.



Desconhece-se a existência de melhores algoritmos para se resolver um problema NP-completo de tamanho arbitrário se utiliza de um dos seguintes enfoques:
›
›
›
›
›

Aproximação;
Probabilístico;
Casos Particulares;
Heurísticas;
Algoritmo genético.








Baseado em idéias da Evolução Natural
Mantém-se uma população de indivíduos
É realizado o cruzamento entre indivíduos gerando novos indivíduos
Pode haver mutação nos indivíduos
A cada geração faz-se a seleção dos melhores indivíduos para o cruzamento
No decorrer do tempo existiram indivíduos que se destacam



Na solução do