An Lise Caixeiro Viajente

Algoritmo do Caixeiro Viajante
Análise do esforço computacional e Robustez

O problema do caixeiro-viajante é um problema de otimização que, apesar de parecer modesto é, na realidade, muito investigado por estudiosos de diversas áreas. O problema pertence à categoria NP-difícil, ou seja, utilizado para um campo de complexidade exponencial, onde o esforço computacional necessário para a sua resolução cresce exponencialmente com o tamanho do problema.
Assim fica bastante difícil determinar a solução ótima para estes problemas, os métodos de resolução passam pelas heurísticas e outros, do ponto de vista matemático, não asseguram a obtenção de uma solução ótima.
O método mais utilizado se chama k-opt. Nele os k arcos são substituídos, no circuito, por outros k arcos com o objetivo de diminuir a distância total percorrida. Quanto maior for o valor de k, melhor é a precisão do método, mas maior é o esforço computacional.
No algoritmo feito, foi observado que o aumento no valor do n cidades provoca uma muito lenta diminuição na velocidade com que o computador calcula o tempo de cada rota, mas provoca um imensamente grande aumento no tempo total de cálculo. Em outras palavras: a inviabilidade computacional é devida à presença da fatorial na medida do esforço computacional do método da redução. Com efeito, se essa complexidade fosse expressa em termos de um polinómio em n o nosso computador seria perfeitamente capaz de suportar o aumento do n.
Os métodos heurísticos são os principais métodos para resolução do problema do caixeiro viajante. Eles são métodos de solução que muitas vezes se apoiam em uma abordagem intuitiva, na qual a estrutura do problema possa ser considerada e explorada de forma eficiente, para a obtenção de uma solução adequada ao problema. Na maioria das vezes as heurísticas tendem a ser diferentes para um determinado problema, precisando de robustez, ou seja, não conseguem produzir boas soluções para problemas com parecidas com as que já foram