Usuário(a):CelsoS/trabalho 4/Rascunho do Trabalho 4
De Wikipedia, a enciclopédia encyclopedia
O problema do caixeiro-viajante (PCV), «travelling salesman problem (TSP)» (em inglês), é um problema de optimização que, apesar de parecer modesto é, na realidade, um dos mais investigados, por cientistas, matemáticos e investigadores de diversas áreas, tais como: logística, genética e produção, entre outros (Applegate et al., cop. 2006, p. 1).
O problema pertence à categoria NP-difícil, «NP-hard» (em inglês), que o remete para um campo de complexidade exponencial, isto é, o esforço computacional necessário para a sua resolução cresce exponencialmente com o tamanho do problema. Assim, dado que é difícil, se não impossível, determinar a solução óptima desta classe de problemas, os métodos de resolução passam pelas heurísticas e afins que, do ponto de vista matemático, não asseguram a obtenção de uma solução óptima (Cunha, 2002).